1 #!/usr/bin/env python 2 3 """ 4 Translate programs. 5 6 Copyright (C) 2015, 2016 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 """ 21 22 from common import * 23 from encoders import * 24 from os.path import exists, join 25 from os import makedirs 26 import compiler 27 import results 28 29 class Translator(CommonOutput): 30 31 "A program translator." 32 33 def __init__(self, importer, deducer, optimiser, output): 34 self.importer = importer 35 self.deducer = deducer 36 self.optimiser = optimiser 37 self.output = output 38 39 def to_output(self): 40 output = join(self.output, "src") 41 42 if not exists(output): 43 makedirs(output) 44 45 self.check_output() 46 47 for module in self.importer.modules.values(): 48 if module.name != "native": 49 tm = TranslatedModule(module.name, self.importer, self.deducer, self.optimiser) 50 tm.translate(module.filename, join(output, "%s.c" % module.name)) 51 52 # Classes representing intermediate translation results. 53 54 class TranslationResult: 55 56 "An abstract translation result mix-in." 57 58 def get_accessor_kinds(self): 59 return None 60 61 class ReturnRef(TranslationResult): 62 63 "Indicates usage of a return statement." 64 65 pass 66 67 class Expression(results.Result, TranslationResult): 68 69 "A general expression." 70 71 def __init__(self, s): 72 self.s = s 73 def __str__(self): 74 return self.s 75 def __repr__(self): 76 return "Expression(%r)" % self.s 77 78 class TrResolvedNameRef(results.ResolvedNameRef, TranslationResult): 79 80 "A reference to a name in the translation." 81 82 def __init__(self, name, ref, expr=None, parameter=None): 83 results.ResolvedNameRef.__init__(self, name, ref, expr) 84 self.parameter = parameter 85 86 def __str__(self): 87 88 "Return an output representation of the referenced name." 89 90 # For sources, any identified static origin will be constant and thus 91 # usable directly. For targets, no constant should be assigned and thus 92 # the alias (or any plain name) will be used. 93 94 ref = self.static() 95 origin = ref and self.get_origin() 96 static_name = origin and encode_path(origin) 97 98 # Determine whether a qualified name is involved. 99 100 t = (self.get_name() or self.name).rsplit(".", 1) 101 parent = len(t) > 1 and t[0] or None 102 attrname = encode_path(t[-1]) 103 104 # Assignments. 105 106 if self.expr: 107 108 # Eliminate assignments between constants. 109 110 if ref and isinstance(self.expr, results.ResolvedNameRef) and self.expr.static(): 111 return "" 112 113 # Qualified names must be converted into parent-relative assignments. 114 115 elif parent: 116 return "__store_via_object(&%s, %s, %s)" % ( 117 encode_path(parent), encode_symbol("pos", attrname), self.expr) 118 119 # All other assignments involve the names as they were given. 120 121 else: 122 return "(%s%s) = %s" % (self.parameter and "*" or "", attrname, self.expr) 123 124 # Expressions. 125 126 elif static_name: 127 parent = ref.parent() 128 context = ref.has_kind("<function>") and encode_path(parent) or None 129 return "((__attr) {%s, &%s})" % (context and "&%s" % context or "0", static_name) 130 131 # Qualified names must be converted into parent-relative accesses. 132 133 elif parent: 134 return "__load_via_object(&%s, %s)" % ( 135 encode_path(parent), encode_symbol("pos", attrname)) 136 137 # All other accesses involve the names as they were given. 138 139 else: 140 return "(%s%s)" % (self.parameter and "*" or "", attrname) 141 142 class TrConstantValueRef(results.ConstantValueRef, TranslationResult): 143 144 "A constant value reference in the translation." 145 146 def __str__(self): 147 return encode_literal_constant(self.number) 148 149 class TrLiteralSequenceRef(results.LiteralSequenceRef, TranslationResult): 150 151 "A reference representing a sequence of values." 152 153 def __str__(self): 154 return str(self.node) 155 156 class AttrResult(Expression, TranslationResult): 157 158 "A translation result for an attribute access." 159 160 def __init__(self, s, refs, accessor_kinds): 161 Expression.__init__(self, s) 162 self.refs = refs 163 self.accessor_kinds = accessor_kinds 164 165 def get_origin(self): 166 return self.refs and len(self.refs) == 1 and first(self.refs).get_origin() 167 168 def has_kind(self, kinds): 169 if not self.refs: 170 return False 171 for ref in self.refs: 172 if ref.has_kind(kinds): 173 return True 174 return False 175 176 def get_accessor_kinds(self): 177 return self.accessor_kinds 178 179 def __repr__(self): 180 return "AttrResult(%r, %r)" % (self.s, self.get_origin()) 181 182 class PredefinedConstantRef(AttrResult): 183 184 "A predefined constant reference." 185 186 def __init__(self, value): 187 self.value = value 188 189 def __str__(self): 190 if self.value in ("False", "True"): 191 return encode_path("__builtins__.boolean.%s" % self.value) 192 elif self.value == "None": 193 return encode_path("__builtins__.none.%s" % self.value) 194 elif self.value == "NotImplemented": 195 return encode_path("__builtins__.notimplemented.%s" % self.value) 196 else: 197 return self.value 198 199 def __repr__(self): 200 return "PredefinedConstantRef(%r)" % self.value 201 202 class BooleanResult(Expression, TranslationResult): 203 204 "A expression producing a boolean result." 205 206 def __str__(self): 207 return "__builtins___bool_bool(%s)" % self.s 208 209 def __repr__(self): 210 return "BooleanResult(%r)" % self.s 211 212 def make_expression(expr): 213 214 "Make a new expression from the existing 'expr'." 215 216 if isinstance(expr, results.Result): 217 return expr 218 else: 219 return Expression(str(expr)) 220 221 # The actual translation process itself. 222 223 class TranslatedModule(CommonModule): 224 225 "A module translator." 226 227 def __init__(self, name, importer, deducer, optimiser): 228 CommonModule.__init__(self, name, importer) 229 self.deducer = deducer 230 self.optimiser = optimiser 231 232 # Output stream. 233 234 self.out = None 235 self.indent = 0 236 self.tabstop = " " 237 238 # Recorded namespaces. 239 240 self.namespaces = [] 241 self.in_conditional = False 242 243 # Exception raising adjustments. 244 245 self.in_try_finally = False 246 self.in_try_except = False 247 248 # Attribute access and accessor counting. 249 250 self.attr_accesses = {} 251 self.attr_accessors = {} 252 253 def __repr__(self): 254 return "TranslatedModule(%r, %r)" % (self.name, self.importer) 255 256 def translate(self, filename, output_filename): 257 258 """ 259 Parse the file having the given 'filename', writing the translation to 260 the given 'output_filename'. 261 """ 262 263 self.parse_file(filename) 264 265 # Collect function namespaces for separate processing. 266 267 self.record_namespaces(self.astnode) 268 269 # Reset the lambda naming (in order to obtain the same names again) and 270 # translate the program. 271 272 self.reset_lambdas() 273 274 self.out = open(output_filename, "w") 275 try: 276 self.start_output() 277 278 # Process namespaces, writing the translation. 279 280 for path, node in self.namespaces: 281 self.process_namespace(path, node) 282 283 # Process the module namespace including class namespaces. 284 285 self.process_namespace([], self.astnode) 286 287 finally: 288 self.out.close() 289 290 def have_object(self): 291 292 "Return whether a namespace is a recorded object." 293 294 return self.importer.objects.get(self.get_namespace_path()) 295 296 def get_builtin_class(self, name): 297 298 "Return a reference to the actual object providing 'name'." 299 300 # NOTE: This makes assumptions about the __builtins__ structure. 301 302 return self.importer.get_object("__builtins__.%s.%s" % (name, name)) 303 304 def is_method(self, path): 305 306 "Return whether 'path' is a method." 307 308 class_name, method_name = path.rsplit(".", 1) 309 return self.importer.classes.has_key(class_name) and class_name or None 310 311 def in_method(self): 312 313 "Return whether the current namespace provides a method." 314 315 return self.in_function and self.is_method(self.get_namespace_path()) 316 317 # Namespace recording. 318 319 def record_namespaces(self, node): 320 321 "Process the program structure 'node', recording namespaces." 322 323 for n in node.getChildNodes(): 324 self.record_namespaces_in_node(n) 325 326 def record_namespaces_in_node(self, node): 327 328 "Process the program structure 'node', recording namespaces." 329 330 # Function namespaces within modules, classes and other functions. 331 # Functions appearing within conditional statements are given arbitrary 332 # names. 333 334 if isinstance(node, compiler.ast.Function): 335 self.record_function_node(node, (self.in_conditional or self.in_function) and self.get_lambda_name() or node.name) 336 337 elif isinstance(node, compiler.ast.Lambda): 338 self.record_function_node(node, self.get_lambda_name()) 339 340 # Classes are visited, but may be ignored if inside functions. 341 342 elif isinstance(node, compiler.ast.Class): 343 self.enter_namespace(node.name) 344 if self.have_object(): 345 self.record_namespaces(node) 346 self.exit_namespace() 347 348 # Conditional nodes are tracked so that function definitions may be 349 # handled. Since "for" loops are converted to "while" loops, they are 350 # included here. 351 352 elif isinstance(node, (compiler.ast.For, compiler.ast.If, compiler.ast.While)): 353 in_conditional = self.in_conditional 354 self.in_conditional = True 355 self.record_namespaces(node) 356 self.in_conditional = in_conditional 357 358 # All other nodes are processed depth-first. 359 360 else: 361 self.record_namespaces(node) 362 363 def record_function_node(self, n, name): 364 365 """ 366 Record the given function, lambda, if expression or list comprehension 367 node 'n' with the given 'name'. 368 """ 369 370 self.in_function = True 371 self.enter_namespace(name) 372 373 if self.have_object(): 374 375 # Record the namespace path and the node itself. 376 377 self.namespaces.append((self.namespace_path[:], n)) 378 self.record_namespaces_in_node(n.code) 379 380 self.exit_namespace() 381 self.in_function = False 382 383 # Constant referencing. 384 385 def get_literal_instance(self, n, name): 386 387 """ 388 For node 'n', return a reference for the type of the given 'name'. 389 """ 390 391 ref = self.get_builtin_class(name) 392 393 if name in ("dict", "list", "tuple"): 394 return self.process_literal_sequence_node(n, name, ref, TrLiteralSequenceRef) 395 else: 396 path = self.get_namespace_path() 397 local_number = self.importer.all_constants[path][n.value] 398 constant_name = "$c%d" % local_number 399 objpath = self.get_object_path(constant_name) 400 number = self.optimiser.constant_numbers[objpath] 401 return TrConstantValueRef(constant_name, ref.instance_of(), n.value, number) 402 403 # Namespace translation. 404 405 def process_namespace(self, path, node): 406 407 """ 408 Process the namespace for the given 'path' defined by the given 'node'. 409 """ 410 411 self.namespace_path = path 412 413 if isinstance(node, (compiler.ast.Function, compiler.ast.Lambda)): 414 self.in_function = True 415 self.process_function_body_node(node) 416 else: 417 self.in_function = False 418 self.function_target = 0 419 self.start_module() 420 self.process_structure(node) 421 self.end_module() 422 423 def process_structure(self, node): 424 425 "Process the given 'node' or result." 426 427 # Handle processing requests on results. 428 429 if isinstance(node, results.Result): 430 return node 431 432 # Handle processing requests on nodes. 433 434 else: 435 l = CommonModule.process_structure(self, node) 436 437 # Return indications of return statement usage. 438 439 if l and isinstance(l[-1], ReturnRef): 440 return l[-1] 441 else: 442 return None 443 444 def process_structure_node(self, n): 445 446 "Process the individual node 'n'." 447 448 # Plain statements emit their expressions. 449 450 if isinstance(n, compiler.ast.Discard): 451 expr = self.process_structure_node(n.expr) 452 self.statement(expr) 453 454 # Nodes using operator module functions. 455 456 elif isinstance(n, compiler.ast.Operator): 457 return self.process_operator_node(n) 458 459 elif isinstance(n, compiler.ast.AugAssign): 460 self.process_augassign_node(n) 461 462 elif isinstance(n, compiler.ast.Compare): 463 return self.process_compare_node(n) 464 465 elif isinstance(n, compiler.ast.Slice): 466 return self.process_slice_node(n) 467 468 elif isinstance(n, compiler.ast.Sliceobj): 469 return self.process_sliceobj_node(n) 470 471 elif isinstance(n, compiler.ast.Subscript): 472 return self.process_subscript_node(n) 473 474 # Classes are visited, but may be ignored if inside functions. 475 476 elif isinstance(n, compiler.ast.Class): 477 self.process_class_node(n) 478 479 # Functions within namespaces have any dynamic defaults initialised. 480 481 elif isinstance(n, compiler.ast.Function): 482 self.process_function_node(n) 483 484 # Lambdas are replaced with references to separately-generated 485 # functions. 486 487 elif isinstance(n, compiler.ast.Lambda): 488 return self.process_lambda_node(n) 489 490 # Assignments. 491 492 elif isinstance(n, compiler.ast.Assign): 493 494 # Handle each assignment node. 495 496 for node in n.nodes: 497 self.process_assignment_node(node, n.expr) 498 499 # Accesses. 500 501 elif isinstance(n, compiler.ast.Getattr): 502 return self.process_attribute_access(n) 503 504 # Names. 505 506 elif isinstance(n, compiler.ast.Name): 507 return self.process_name_node(n) 508 509 # Loops and conditionals. 510 511 elif isinstance(n, compiler.ast.For): 512 self.process_for_node(n) 513 514 elif isinstance(n, compiler.ast.While): 515 self.process_while_node(n) 516 517 elif isinstance(n, compiler.ast.If): 518 self.process_if_node(n) 519 520 elif isinstance(n, (compiler.ast.And, compiler.ast.Or)): 521 return self.process_logical_node(n) 522 523 elif isinstance(n, compiler.ast.Not): 524 return self.process_not_node(n) 525 526 # Exception control-flow tracking. 527 528 elif isinstance(n, compiler.ast.TryExcept): 529 self.process_try_node(n) 530 531 elif isinstance(n, compiler.ast.TryFinally): 532 self.process_try_finally_node(n) 533 534 # Control-flow modification statements. 535 536 elif isinstance(n, compiler.ast.Break): 537 self.writestmt("break;") 538 539 elif isinstance(n, compiler.ast.Continue): 540 self.writestmt("continue;") 541 542 elif isinstance(n, compiler.ast.Raise): 543 self.process_raise_node(n) 544 545 elif isinstance(n, compiler.ast.Return): 546 return self.process_return_node(n) 547 548 # Print statements. 549 550 elif isinstance(n, (compiler.ast.Print, compiler.ast.Printnl)): 551 self.statement(self.process_print_node(n)) 552 553 # Invocations. 554 555 elif isinstance(n, compiler.ast.CallFunc): 556 return self.process_invocation_node(n) 557 558 elif isinstance(n, compiler.ast.Keyword): 559 return self.process_structure_node(n.expr) 560 561 # Constant usage. 562 563 elif isinstance(n, compiler.ast.Const): 564 return self.get_literal_instance(n, n.value.__class__.__name__) 565 566 elif isinstance(n, compiler.ast.Dict): 567 return self.get_literal_instance(n, "dict") 568 569 elif isinstance(n, compiler.ast.List): 570 return self.get_literal_instance(n, "list") 571 572 elif isinstance(n, compiler.ast.Tuple): 573 return self.get_literal_instance(n, "tuple") 574 575 # All other nodes are processed depth-first. 576 577 else: 578 return self.process_structure(n) 579 580 def process_assignment_node(self, n, expr): 581 582 "Process the individual node 'n' to be assigned the contents of 'expr'." 583 584 # Names and attributes are assigned the entire expression. 585 586 if isinstance(n, compiler.ast.AssName): 587 name_ref = self.process_name_node(n, self.process_structure_node(expr)) 588 self.statement(name_ref) 589 590 # Employ guards after assignments if required. 591 592 if expr and name_ref.is_name(): 593 self.generate_guard(name_ref.name) 594 595 elif isinstance(n, compiler.ast.AssAttr): 596 in_assignment = self.in_assignment 597 self.in_assignment = self.process_structure_node(expr) 598 self.statement(self.process_attribute_access(n)) 599 self.in_assignment = in_assignment 600 601 # Lists and tuples are matched against the expression and their 602 # items assigned to expression items. 603 604 elif isinstance(n, (compiler.ast.AssList, compiler.ast.AssTuple)): 605 self.process_assignment_node_items(n, expr) 606 607 # Slices and subscripts are permitted within assignment nodes. 608 609 elif isinstance(n, compiler.ast.Slice): 610 self.statement(self.process_slice_node(n, expr)) 611 612 elif isinstance(n, compiler.ast.Subscript): 613 self.statement(self.process_subscript_node(n, expr)) 614 615 def process_attribute_access(self, n): 616 617 """ 618 Process the given attribute access node 'n'. 619 620 Where a name is provided, a single access should be recorded 621 involving potentially many attributes, thus providing a path to an 622 object. The remaining attributes are then accessed dynamically. 623 The remaining accesses could be deduced and computed, but they would 624 also need to be tested. 625 626 Where no name is provided, potentially many accesses should be 627 recorded, one per attribute name. These could be used to provide 628 computed accesses, but the accessors would need to be tested in each 629 case. 630 """ 631 632 # Obtain any completed chain and return the reference to it. 633 634 attr_expr = self.process_attribute_chain(n) 635 if self.have_access_expression(n): 636 return attr_expr 637 638 # Where the start of the chain of attributes has been reached, process 639 # the complete access. 640 641 name_ref = attr_expr and attr_expr.is_name() and attr_expr 642 name = name_ref and self.get_name_for_tracking(name_ref.name, name_ref and name_ref.final()) or None 643 644 location = self.get_access_location(name) 645 refs = self.get_referenced_attributes(location) 646 647 # Generate access instructions. 648 649 subs = { 650 "<expr>" : str(attr_expr), 651 "<assexpr>" : str(self.in_assignment), 652 "<context>" : "__tmp_context", 653 "<accessor>" : "__tmp_value", 654 } 655 656 output = [] 657 658 for instruction in self.optimiser.access_instructions[location]: 659 output.append(encode_access_instruction(instruction, subs)) 660 661 if len(output) == 1: 662 out = output[0] 663 else: 664 out = "(\n%s\n)" % ",\n".join(output) 665 666 del self.attrs[0] 667 return AttrResult(out, refs, self.get_accessor_kinds(location)) 668 669 def get_referenced_attributes(self, location): 670 671 """ 672 Convert 'location' to the form used by the deducer and retrieve any 673 identified attribute. 674 """ 675 676 access_location = self.deducer.const_accesses.get(location) 677 refs = [] 678 for attrtype, objpath, attr in self.deducer.referenced_attrs[access_location or location]: 679 refs.append(attr) 680 return refs 681 682 def get_accessor_kinds(self, location): 683 684 "Return the accessor kinds for 'location'." 685 686 return self.optimiser.accessor_kinds[location] 687 688 def get_access_location(self, name): 689 690 """ 691 Using the current namespace and the given 'name', return the access 692 location. 693 """ 694 695 path = self.get_path_for_access() 696 697 # Get the location used by the deducer and optimiser and find any 698 # recorded access. 699 700 attrnames = ".".join(self.attrs) 701 access_number = self.get_access_number(path, name, attrnames) 702 self.update_access_number(path, name, attrnames) 703 return (path, name, attrnames, access_number) 704 705 def get_access_number(self, path, name, attrnames): 706 access = name, attrnames 707 if self.attr_accesses.has_key(path) and self.attr_accesses[path].has_key(access): 708 return self.attr_accesses[path][access] 709 else: 710 return 0 711 712 def update_access_number(self, path, name, attrnames): 713 access = name, attrnames 714 if name: 715 init_item(self.attr_accesses, path, dict) 716 init_item(self.attr_accesses[path], access, lambda: 0) 717 self.attr_accesses[path][access] += 1 718 719 def get_accessor_location(self, name): 720 721 """ 722 Using the current namespace and the given 'name', return the accessor 723 location. 724 """ 725 726 path = self.get_path_for_access() 727 728 # Get the location used by the deducer and optimiser and find any 729 # recorded accessor. 730 731 access_number = self.get_accessor_number(path, name) 732 self.update_accessor_number(path, name) 733 return (path, name, None, access_number) 734 735 def get_accessor_number(self, path, name): 736 if self.attr_accessors.has_key(path) and self.attr_accessors[path].has_key(name): 737 return self.attr_accessors[path][name] 738 else: 739 return 0 740 741 def update_accessor_number(self, path, name): 742 if name: 743 init_item(self.attr_accessors, path, dict) 744 init_item(self.attr_accessors[path], name, lambda: 0) 745 self.attr_accessors[path][name] += 1 746 747 def process_class_node(self, n): 748 749 "Process the given class node 'n'." 750 751 self.enter_namespace(n.name) 752 753 if self.have_object(): 754 class_name = self.get_namespace_path() 755 self.write_comment("Class: %s" % class_name) 756 757 self.initialise_inherited_members(class_name) 758 759 self.process_structure(n) 760 self.write_comment("End class: %s" % class_name) 761 762 self.exit_namespace() 763 764 def initialise_inherited_members(self, class_name): 765 766 "Initialise members of 'class_name' inherited from its ancestors." 767 768 for name, path in self.importer.all_class_attrs[class_name].items(): 769 target = "%s.%s" % (class_name, name) 770 771 # Ignore attributes with definitions. 772 773 ref = self.importer.identify(target) 774 if ref: 775 continue 776 777 # Reference inherited attributes. 778 779 ref = self.importer.identify(path) 780 if ref and not ref.static(): 781 parent, attrname = path.rsplit(".", 1) 782 783 self.writestmt("__store_via_object(&%s, %s, __load_via_object(&%s, %s));" % ( 784 encode_path(class_name), encode_symbol("pos", name), 785 encode_path(parent), encode_symbol("pos", attrname) 786 )) 787 788 def process_function_body_node(self, n): 789 790 """ 791 Process the given function, lambda, if expression or list comprehension 792 node 'n', generating the body. 793 """ 794 795 function_name = self.get_namespace_path() 796 self.start_function(function_name) 797 798 # Process the function body. 799 800 in_conditional = self.in_conditional 801 self.in_conditional = False 802 self.function_target = 0 803 804 # Process any guards defined for the parameters. 805 806 for name in self.importer.function_parameters.get(function_name): 807 self.generate_guard(name) 808 809 # Produce the body and any additional return statement. 810 811 expr = self.process_structure_node(n.code) or PredefinedConstantRef("None") 812 if not isinstance(expr, ReturnRef): 813 self.writestmt("return %s;" % expr) 814 815 self.in_conditional = in_conditional 816 817 self.end_function(function_name) 818 819 def generate_guard(self, name): 820 821 """ 822 Get the accessor details for 'name', found in the current namespace, and 823 generate any guards defined for it. 824 """ 825 826 # Obtain the location, keeping track of assignment versions. 827 828 location = self.get_accessor_location(name) 829 test = self.deducer.accessor_guard_tests.get(location) 830 831 # Generate any guard from the deduced information. 832 833 if test: 834 guard, guard_type = test 835 836 if guard == "specific": 837 ref = first(self.deducer.accessor_all_types[location]) 838 argstr = "&%s" % encode_path(ref.get_origin()) 839 elif guard == "common": 840 ref = first(self.deducer.accessor_all_general_types[location]) 841 typeattr = encode_type_attribute(ref.get_origin()) 842 argstr = "%s, %s" % (encode_symbol("pos", typeattr), encode_symbol("code", typeattr)) 843 else: 844 return 845 846 # Produce an appropriate access to an attribute's value. 847 848 parameters = self.importer.function_parameters.get(self.get_namespace_path()) 849 if parameters and name in parameters: 850 name_to_value = "%s->value" % name 851 else: 852 name_to_value = "%s.value" % name 853 854 # Write a test that raises a TypeError upon failure. 855 856 self.writestmt("if (!__test_%s_%s(%s, %s)) __raise_type_error();" % ( 857 guard, guard_type, name_to_value, argstr)) 858 859 def process_function_node(self, n): 860 861 """ 862 Process the given function, lambda, if expression or list comprehension 863 node 'n', generating any initialisation statements. 864 """ 865 866 # Where a function is declared conditionally, use a separate name for 867 # the definition, and assign the definition to the stated name. 868 869 original_name = n.name 870 871 if self.in_conditional or self.in_function: 872 name = self.get_lambda_name() 873 else: 874 name = n.name 875 876 objpath = self.get_object_path(name) 877 878 # Obtain details of the defaults. 879 880 defaults = self.process_function_defaults(n, name, objpath) 881 if defaults: 882 for default in defaults: 883 self.writeline("%s;" % default) 884 885 # Where a function is set conditionally or where the name may refer to 886 # different values, assign the name. 887 888 ref = self.importer.identify(objpath) 889 890 if self.in_conditional or self.in_function: 891 self.process_assignment_for_function(original_name, compiler.ast.Name(name)) 892 elif not ref.static(): 893 context = self.is_method(objpath) 894 895 self.process_assignment_for_function(original_name, 896 make_expression("((__attr) {%s, &%s})" % ( 897 context and "&%s" % encode_path(context) or "0", 898 encode_path(objpath)))) 899 900 def process_function_defaults(self, n, name, objpath, instance_name=None): 901 902 """ 903 Process the given function or lambda node 'n', initialising defaults 904 that are dynamically set. The given 'name' indicates the name of the 905 function. The given 'objpath' indicates the origin of the function. 906 The given 'instance_name' indicates the name of any separate instance 907 of the function created to hold the defaults. 908 909 Return a list of operations setting defaults on a function instance. 910 """ 911 912 function_name = self.get_object_path(name) 913 function_defaults = self.importer.function_defaults.get(function_name) 914 if not function_defaults: 915 return None 916 917 # Determine whether any unidentified defaults are involved. 918 919 for argname, default in function_defaults: 920 if not default.static(): 921 break 922 else: 923 return None 924 925 # Handle bound methods. 926 927 if not instance_name: 928 if self.is_method(objpath): 929 instance_name = "&%s" % encode_bound_reference(objpath) 930 else: 931 instance_name = "&%s" % encode_path(objpath) 932 933 # Where defaults are involved but cannot be identified, obtain a new 934 # instance of the lambda and populate the defaults. 935 936 defaults = [] 937 938 # Join the original defaults with the inspected defaults. 939 940 original_defaults = [(argname, default) for (argname, default) in compiler.ast.get_defaults(n) if default] 941 942 for i, (original, inspected) in enumerate(map(None, original_defaults, function_defaults)): 943 944 # Obtain any reference for the default. 945 946 if original: 947 argname, default = original 948 name_ref = self.process_structure_node(default) 949 elif inspected: 950 argname, default = inspected 951 name_ref = TrResolvedNameRef(argname, default) 952 else: 953 continue 954 955 if name_ref: 956 defaults.append("__SETDEFAULT(%s, %s, %s)" % (instance_name, i, name_ref)) 957 958 return defaults 959 960 def process_if_node(self, n): 961 962 """ 963 Process the given "if" node 'n'. 964 """ 965 966 first = True 967 for test, body in n.tests: 968 test_ref = self.process_structure_node(test) 969 self.start_if(first, test_ref) 970 971 in_conditional = self.in_conditional 972 self.in_conditional = True 973 self.process_structure_node(body) 974 self.in_conditional = in_conditional 975 976 self.end_if() 977 first = False 978 979 if n.else_: 980 self.start_else() 981 self.process_structure_node(n.else_) 982 self.end_else() 983 984 def process_invocation_node(self, n): 985 986 "Process the given invocation node 'n'." 987 988 expr = self.process_structure_node(n.node) 989 objpath = expr.get_origin() 990 target = None 991 function = None 992 literal_instantiation = False 993 context_required = True 994 995 # Obtain details of the callable. 996 997 # Literals may be instantiated specially. 998 999 if expr.is_name() and expr.name.startswith("$L") and objpath: 1000 literal_instantiation = True 1001 parameters = None 1002 target = encode_literal_instantiator(objpath) 1003 context_required = False 1004 1005 # Identified targets employ function pointers directly. 1006 1007 elif objpath: 1008 parameters = self.importer.function_parameters.get(objpath) 1009 1010 # Class invocation involves instantiators. 1011 1012 if expr.has_kind("<class>"): 1013 target = encode_instantiator_pointer(objpath) 1014 target_structure = "&%s" % encode_bound_reference("%s.__init__" % objpath) 1015 context_required = False 1016 1017 # Only plain functions and bound methods employ function pointers. 1018 1019 elif expr.has_kind("<function>"): 1020 function = objpath 1021 1022 # Test for functions and methods. 1023 1024 method_class = self.is_method(objpath) 1025 accessor_kinds = expr.get_accessor_kinds() 1026 instance_accessor = accessor_kinds and \ 1027 len(accessor_kinds) == 1 and \ 1028 first(accessor_kinds) == "<instance>" 1029 1030 if not method_class or instance_accessor: 1031 target = encode_function_pointer(objpath) 1032 target_structure = self.is_method(objpath) and \ 1033 encode_bound_reference(objpath) or \ 1034 "&%s" % encode_path(objpath) 1035 1036 if not method_class: 1037 context_required = False 1038 1039 # Other targets are retrieved at run-time. 1040 1041 else: 1042 parameters = None 1043 1044 # Arguments are presented in a temporary frame array with any context 1045 # always being the first argument. Where it would be unused, it may be 1046 # set to null. 1047 1048 if context_required: 1049 args = ["__CONTEXT_AS_VALUE(__tmp_targets[%d])" % self.function_target] 1050 else: 1051 args = ["(__attr) {0, 0}"] 1052 1053 args += [None] * (not parameters and len(n.args) or parameters and len(parameters) or 0) 1054 kwcodes = [] 1055 kwargs = [] 1056 1057 # Any invocations in the arguments will store target details in a 1058 # different location. 1059 1060 self.function_target += 1 1061 1062 for i, arg in enumerate(n.args): 1063 argexpr = self.process_structure_node(arg) 1064 1065 # Store a keyword argument, either in the argument list or 1066 # in a separate keyword argument list for subsequent lookup. 1067 1068 if isinstance(arg, compiler.ast.Keyword): 1069 1070 # With knowledge of the target, store the keyword 1071 # argument directly. 1072 1073 if parameters: 1074 argnum = parameters.index(arg.name) 1075 args[argnum+1] = str(argexpr) 1076 1077 # Otherwise, store the details in a separate collection. 1078 1079 else: 1080 kwargs.append(str(argexpr)) 1081 kwcodes.append("{%s, %s}" % ( 1082 encode_symbol("ppos", arg.name), 1083 encode_symbol("pcode", arg.name))) 1084 1085 # Store non-keyword arguments in the argument list, rejecting 1086 # superfluous arguments. 1087 1088 else: 1089 try: 1090 args[i+1] = str(argexpr) 1091 except IndexError: 1092 raise TranslateError("Too many arguments specified.", 1093 self.get_namespace_path(), n) 1094 1095 # Reference the current target again. 1096 1097 self.function_target -= 1 1098 1099 # Defaults are added to the frame where arguments are missing. 1100 1101 if parameters: 1102 function_defaults = self.importer.function_defaults.get(objpath) 1103 if function_defaults: 1104 1105 # Visit each default and set any missing arguments. 1106 # Use the target structure to obtain defaults, as opposed to the 1107 # actual function involved. 1108 1109 for i, (argname, default) in enumerate(function_defaults): 1110 argnum = parameters.index(argname) 1111 if not args[argnum+1]: 1112 args[argnum+1] = "__GETDEFAULT(%s, %d)" % (target_structure, i) 1113 1114 # Test for missing arguments. 1115 1116 if None in args: 1117 raise TranslateError("Not all arguments supplied.", 1118 self.get_namespace_path(), n) 1119 1120 # Encode the arguments. 1121 1122 argstr = "__ARGS(%s)" % ", ".join(args) 1123 kwargstr = kwargs and ("__ARGS(%s)" % ", ".join(kwargs)) or "0" 1124 kwcodestr = kwcodes and ("__KWARGS(%s)" % ", ".join(kwcodes)) or "0" 1125 1126 # Where literal instantiation is occurring, add an argument indicating 1127 # the number of values. 1128 1129 if literal_instantiation: 1130 argstr += ", %d" % (len(args) - 1) 1131 1132 # First, the invocation expression is presented. 1133 1134 stages = [] 1135 1136 # Without a known specific callable, the expression provides the target. 1137 1138 if not target or context_required: 1139 stages.append("__tmp_targets[%d] = %s" % (self.function_target, expr)) 1140 1141 # Any specific callable is then obtained. 1142 1143 if target: 1144 stages.append(target) 1145 elif function: 1146 stages.append("__load_via_object(__tmp_targets[%d].value, %s).fn" % ( 1147 self.function_target, encode_symbol("pos", "__fn__"))) 1148 1149 # With a known target, the function is obtained directly and called. 1150 1151 if target or function: 1152 output = "(\n%s\n)(%s)" % (",\n".join(stages), argstr) 1153 1154 # With unknown targets, the generic invocation function is applied to 1155 # the callable and argument collections. 1156 1157 else: 1158 output = "(%s, __invoke(\n__tmp_targets[%d],\n%d, %d, %s, %s,\n%d, %s\n))" % ( 1159 ",\n".join(stages), 1160 self.function_target, 1161 self.always_callable and 1 or 0, 1162 len(kwargs), kwcodestr, kwargstr, 1163 len(args), argstr) 1164 1165 return make_expression(output) 1166 1167 def always_callable(self, refs): 1168 1169 "Determine whether all 'refs' are callable." 1170 1171 for ref in refs: 1172 if not ref.static(): 1173 return False 1174 else: 1175 origin = ref.final() 1176 if not self.importer.get_attribute(origin, "__fn__"): 1177 return False 1178 return True 1179 1180 def need_default_arguments(self, objpath, nargs): 1181 1182 """ 1183 Return whether any default arguments are needed when invoking the object 1184 given by 'objpath'. 1185 """ 1186 1187 parameters = self.importer.function_parameters.get(objpath) 1188 return nargs < len(parameters) 1189 1190 def process_lambda_node(self, n): 1191 1192 "Process the given lambda node 'n'." 1193 1194 name = self.get_lambda_name() 1195 function_name = self.get_object_path(name) 1196 1197 defaults = self.process_function_defaults(n, name, function_name, "__tmp_value") 1198 1199 # Without defaults, produce an attribute referring to the function. 1200 1201 if not defaults: 1202 return make_expression("((__attr) {0, &%s})" % encode_path(function_name)) 1203 1204 # With defaults, copy the function structure and set the defaults on the 1205 # copy. 1206 1207 else: 1208 return make_expression("(__tmp_value = __COPY(&%s, sizeof(%s)), %s, (__attr) {0, __tmp_value})" % ( 1209 encode_path(function_name), 1210 encode_symbol("obj", function_name), 1211 ", ".join(defaults))) 1212 1213 def process_logical_node(self, n): 1214 1215 """ 1216 Process the given operator node 'n'. 1217 1218 Convert ... to ... 1219 1220 <a> and <b> 1221 (__tmp_result = <a>, !__BOOL(__tmp_result)) ? __tmp_result : <b> 1222 1223 <a> or <b> 1224 (__tmp_result = <a>, __BOOL(__tmp_result)) ? __tmp_result : <b> 1225 """ 1226 1227 if isinstance(n, compiler.ast.And): 1228 op = "!" 1229 else: 1230 op = "" 1231 1232 results = [] 1233 1234 for node in n.nodes[:-1]: 1235 expr = self.process_structure_node(node) 1236 results.append("(__tmp_result = %s, %s__BOOL(__tmp_result)) ? __tmp_result : " % (expr, op)) 1237 1238 expr = self.process_structure_node(n.nodes[-1]) 1239 results.append(str(expr)) 1240 1241 return make_expression("(%s)" % "".join(results)) 1242 1243 def process_name_node(self, n, expr=None): 1244 1245 "Process the given name node 'n' with the optional assignment 'expr'." 1246 1247 # Determine whether the name refers to a static external entity. 1248 1249 if n.name in predefined_constants: 1250 return PredefinedConstantRef(n.name) 1251 1252 # Convert literal references, operator function names, and print 1253 # function names to references. 1254 1255 elif n.name.startswith("$L") or n.name.startswith("$op") or \ 1256 n.name.startswith("$print"): 1257 ref = self.importer.get_module(self.name).special.get(n.name) 1258 return TrResolvedNameRef(n.name, ref) 1259 1260 # Get the appropriate name for the name reference, using the same method 1261 # as in the inspector. 1262 1263 path = self.get_namespace_path() 1264 objpath = self.get_object_path(n.name) 1265 1266 # Determine any assigned globals. 1267 1268 globals = self.importer.get_module(self.name).scope_globals.get(path) 1269 if globals and n.name in globals: 1270 objpath = self.get_global_path(n.name) 1271 1272 # Get the static identity of the name. 1273 1274 ref = self.importer.identify(objpath) 1275 if ref and not ref.get_name(): 1276 ref = ref.alias(objpath) 1277 1278 # Obtain any resolved names for non-assignment names. 1279 1280 if not expr and not ref and self.in_function: 1281 locals = self.importer.function_locals.get(path) 1282 ref = locals and locals.get(n.name) 1283 1284 # Determine whether the name refers to a parameter. The generation of 1285 # parameter references is different from other names. 1286 1287 parameters = self.importer.function_parameters.get(path) 1288 parameter = n.name == "self" and self.in_method() or \ 1289 parameters and n.name in parameters 1290 1291 # Qualified names are used for resolved static references or for 1292 # static namespace members. The reference should be configured to return 1293 # such names. 1294 1295 return TrResolvedNameRef(n.name, ref, expr=expr, parameter=parameter) 1296 1297 def process_not_node(self, n): 1298 1299 "Process the given operator node 'n'." 1300 1301 return make_expression("(__BOOL(%s) ? %s : %s)" % 1302 (self.process_structure_node(n.expr), PredefinedConstantRef("False"), 1303 PredefinedConstantRef("True"))) 1304 1305 def process_raise_node(self, n): 1306 1307 "Process the given raise node 'n'." 1308 1309 # NOTE: Determine which raise statement variants should be permitted. 1310 1311 if n.expr1: 1312 self.writestmt("__Raise(%s);" % self.process_structure_node(n.expr1)) 1313 else: 1314 self.writestmt("__Complete;") 1315 1316 def process_return_node(self, n): 1317 1318 "Process the given return node 'n'." 1319 1320 expr = self.process_structure_node(n.value) or PredefinedConstantRef("None") 1321 if self.in_try_finally or self.in_try_except: 1322 self.writestmt("__Return(%s);" % expr) 1323 else: 1324 self.writestmt("return %s;" % expr) 1325 1326 return ReturnRef() 1327 1328 def process_try_node(self, n): 1329 1330 """ 1331 Process the given "try...except" node 'n'. 1332 """ 1333 1334 in_try_except = self.in_try_except 1335 self.in_try_except = True 1336 1337 # Use macros to implement exception handling. 1338 1339 self.writestmt("__Try") 1340 self.writeline("{") 1341 self.indent += 1 1342 self.process_structure_node(n.body) 1343 1344 # Put the else statement in another try block that handles any raised 1345 # exceptions and converts them to exceptions that will not be handled by 1346 # the main handling block. 1347 1348 if n.else_: 1349 self.writestmt("__Try") 1350 self.writeline("{") 1351 self.indent += 1 1352 self.process_structure_node(n.else_) 1353 self.indent -= 1 1354 self.writeline("}") 1355 self.writeline("__Catch (__tmp_exc)") 1356 self.writeline("{") 1357 self.indent += 1 1358 self.writeline("if (__tmp_exc.raising) __RaiseElse(__tmp_exc.arg);") 1359 self.writeline("else if (__tmp_exc.completing) __Throw(__tmp_exc);") 1360 self.indent -= 1 1361 self.writeline("}") 1362 1363 # Complete the try block and enter the finally block, if appropriate. 1364 1365 if self.in_try_finally: 1366 self.writestmt("__Complete;") 1367 1368 self.indent -= 1 1369 self.writeline("}") 1370 1371 self.in_try_except = in_try_except 1372 1373 # Handlers are tests within a common handler block. 1374 1375 self.writeline("__Catch (__tmp_exc)") 1376 self.writeline("{") 1377 self.indent += 1 1378 1379 # Introduce an if statement to handle the completion of a try block. 1380 1381 self.process_try_completion() 1382 1383 # Handle exceptions in else blocks converted to __RaiseElse, converting 1384 # them back to normal exceptions. 1385 1386 if n.else_: 1387 self.writeline("else if (__tmp_exc.raising_else) __Raise(__tmp_exc.arg);") 1388 1389 # Exception handling. 1390 1391 for name, var, handler in n.handlers: 1392 1393 # Test for specific exceptions. 1394 1395 if name is not None: 1396 name_ref = self.process_structure_node(name) 1397 self.writeline("else if (__BOOL(__fn_native__isinstance((__attr[]) {{0, 0}, __tmp_exc.arg, %s})))" % name_ref) 1398 else: 1399 self.writeline("else if (1)") 1400 1401 self.writeline("{") 1402 self.indent += 1 1403 1404 # Establish the local for the handler. 1405 1406 if var is not None: 1407 self.writestmt("%s;" % self.process_name_node(var, make_expression("__tmp_exc.arg"))) 1408 1409 if handler is not None: 1410 self.process_structure_node(handler) 1411 1412 self.indent -= 1 1413 self.writeline("}") 1414 1415 # Re-raise unhandled exceptions. 1416 1417 self.writeline("else __Throw(__tmp_exc);") 1418 1419 # End the handler block. 1420 1421 self.indent -= 1 1422 self.writeline("}") 1423 1424 def process_try_finally_node(self, n): 1425 1426 """ 1427 Process the given "try...finally" node 'n'. 1428 """ 1429 1430 in_try_finally = self.in_try_finally 1431 self.in_try_finally = True 1432 1433 # Use macros to implement exception handling. 1434 1435 self.writestmt("__Try") 1436 self.writeline("{") 1437 self.indent += 1 1438 self.process_structure_node(n.body) 1439 self.indent -= 1 1440 self.writeline("}") 1441 1442 self.in_try_finally = in_try_finally 1443 1444 # Finally clauses handle special exceptions. 1445 1446 self.writeline("__Catch (__tmp_exc)") 1447 self.writeline("{") 1448 self.indent += 1 1449 self.process_structure_node(n.final) 1450 1451 # Introduce an if statement to handle the completion of a try block. 1452 1453 self.process_try_completion() 1454 self.writeline("else __Throw(__tmp_exc);") 1455 1456 self.indent -= 1 1457 self.writeline("}") 1458 1459 def process_try_completion(self): 1460 1461 "Generate a test for the completion of a try block." 1462 1463 self.writestmt("if (__tmp_exc.completing)") 1464 self.writeline("{") 1465 self.indent += 1 1466 1467 # Only use the normal return statement if no surrounding try blocks 1468 # apply. 1469 1470 if not self.in_try_finally and not self.in_try_except: 1471 self.writeline("if (!__ISNULL(__tmp_exc.arg)) return __tmp_exc.arg;") 1472 else: 1473 self.writeline("if (!__ISNULL(__tmp_exc.arg)) __Throw(__tmp_exc);") 1474 1475 self.indent -= 1 1476 self.writeline("}") 1477 1478 def process_while_node(self, n): 1479 1480 "Process the given while node 'n'." 1481 1482 self.writeline("while (1)") 1483 self.writeline("{") 1484 self.indent += 1 1485 test = self.process_structure_node(n.test) 1486 1487 # Emit the loop termination condition unless "while <true value>" is 1488 # indicated. 1489 1490 if not (isinstance(test, PredefinedConstantRef) and test.value): 1491 1492 # NOTE: This needs to evaluate whether the operand is true or false 1493 # NOTE: according to Python rules. 1494 1495 self.writeline("if (!__BOOL(%s))" % test) 1496 self.writeline("{") 1497 self.indent += 1 1498 if n.else_: 1499 self.process_structure_node(n.else_) 1500 self.writestmt("break;") 1501 self.indent -= 1 1502 self.writeline("}") 1503 1504 in_conditional = self.in_conditional 1505 self.in_conditional = True 1506 self.process_structure_node(n.body) 1507 self.in_conditional = in_conditional 1508 1509 self.indent -= 1 1510 self.writeline("}") 1511 1512 # Output generation. 1513 1514 def start_output(self): 1515 1516 "Write the declarations at the top of each source file." 1517 1518 print >>self.out, """\ 1519 #include "types.h" 1520 #include "exceptions.h" 1521 #include "ops.h" 1522 #include "progconsts.h" 1523 #include "progops.h" 1524 #include "progtypes.h" 1525 #include "main.h" 1526 """ 1527 1528 def start_module(self): 1529 1530 "Write the start of each module's main function." 1531 1532 print >>self.out, "void __main_%s()" % encode_path(self.name) 1533 print >>self.out, "{" 1534 self.indent += 1 1535 self.write_temporaries(self.importer.function_targets.get(self.name)) 1536 1537 def end_module(self): 1538 1539 "End each module by closing its main function." 1540 1541 self.indent -= 1 1542 print >>self.out, "}" 1543 1544 def start_function(self, name): 1545 1546 "Start the function having the given 'name'." 1547 1548 print >>self.out, "__attr %s(__attr __args[])" % encode_function_pointer(name) 1549 print >>self.out, "{" 1550 self.indent += 1 1551 self.write_temporaries(self.importer.function_targets.get(name)) 1552 1553 # Obtain local names from parameters. 1554 1555 parameters = self.importer.function_parameters[name] 1556 locals = self.importer.function_locals[name].keys() 1557 names = [] 1558 1559 for n in locals: 1560 1561 # Filter out special names and parameters. Note that self is a local 1562 # regardless of whether it originally appeared in the parameters or 1563 # not. 1564 1565 if n.startswith("$l") or n in parameters or n == "self": 1566 continue 1567 names.append(encode_path(n)) 1568 1569 # Emit required local names. 1570 1571 if names: 1572 names.sort() 1573 self.writeline("__attr %s;" % ", ".join(names)) 1574 1575 self.write_parameters(name) 1576 1577 def end_function(self, name): 1578 1579 "End the function having the given 'name'." 1580 1581 self.indent -= 1 1582 print >>self.out, "}" 1583 print >>self.out 1584 1585 def write_temporaries(self, targets): 1586 1587 """ 1588 Write temporary storage employed by functions, providing space for the 1589 given number of 'targets'. 1590 """ 1591 1592 targets = targets is not None and "__tmp_targets[%d], " % targets or "" 1593 1594 self.writeline("__ref __tmp_context, __tmp_value;") 1595 self.writeline("__attr %s__tmp_result;" % targets) 1596 self.writeline("__exc __tmp_exc;") 1597 1598 def write_parameters(self, name): 1599 1600 """ 1601 For the function having the given 'name', write definitions of 1602 parameters found in the arguments array. 1603 """ 1604 1605 parameters = self.importer.function_parameters[name] 1606 1607 # Generate any self reference. 1608 1609 if self.is_method(name): 1610 self.writeline("__attr * const self = &__args[0];") 1611 1612 # Generate aliases for the parameters. 1613 1614 for i, parameter in enumerate(parameters): 1615 self.writeline("__attr * const %s = &__args[%d];" % (encode_path(parameter), i+1)) 1616 1617 def start_if(self, first, test_ref): 1618 self.writestmt("%sif (__BOOL(%s))" % (not first and "else " or "", test_ref)) 1619 self.writeline("{") 1620 self.indent += 1 1621 1622 def end_if(self): 1623 self.indent -= 1 1624 self.writeline("}") 1625 1626 def start_else(self): 1627 self.writeline("else") 1628 self.writeline("{") 1629 self.indent += 1 1630 1631 def end_else(self): 1632 self.indent -= 1 1633 self.writeline("}") 1634 1635 def statement(self, expr): 1636 # NOTE: Should never be None. 1637 if not expr: 1638 self.writestmt("...;") 1639 s = str(expr) 1640 if s: 1641 self.writestmt("%s;" % s) 1642 1643 def statements(self, results): 1644 for result in results: 1645 self.statement(result) 1646 1647 def writeline(self, s): 1648 print >>self.out, "%s%s" % (self.pad(), self.indenttext(s, self.indent + 1)) 1649 1650 def writestmt(self, s): 1651 print >>self.out 1652 self.writeline(s) 1653 1654 def write_comment(self, s): 1655 self.writestmt("/* %s */" % s) 1656 1657 def pad(self, extra=0): 1658 return (self.indent + extra) * self.tabstop 1659 1660 def indenttext(self, s, levels): 1661 lines = s.split("\n") 1662 out = [lines[0]] 1663 for line in lines[1:]: 1664 out.append(levels * self.tabstop + line) 1665 if line.endswith("("): 1666 levels += 1 1667 elif line.startswith(")"): 1668 levels -= 1 1669 return "\n".join(out) 1670 1671 # vim: tabstop=4 expandtab shiftwidth=4