1 #!/usr/bin/env python 2 3 """ 4 Perform deductions on an inspected program. 5 6 Copyright (C) 2006, 2007, 2010, 2011, 2012, 2013, 2014 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 micropython.stdcompiler import compiler 23 from compiler.ast import * 24 25 from micropython.basicdata import Constant, TypedInstance 26 from micropython.common import ASTVisitor, used_by_unit 27 from micropython.data import * 28 from micropython.errors import * 29 30 try: 31 set 32 except NameError: 33 from sets import Set as set 34 35 # Source code classes. 36 37 class DeducedSource(ASTVisitor): 38 39 "A module upon which deductions of code behaviour are made." 40 41 def __init__(self, module, program): 42 self.visitor = self 43 self.module = module 44 self.program = program 45 self.objtable = program.get_object_table() 46 self.units = [] 47 self.expr = None 48 49 def get_unit(self): 50 return self.units[-1] 51 52 def get_module(self): 53 return self.units[0] 54 55 def deduce(self): 56 57 "Process the module, making deductions." 58 59 self.dispatch(self.module.astnode) 60 61 def dispatch(self, node, *args): 62 63 "NOTE: From compiler.visitor.ASTVisitor." 64 65 try: 66 return node.visit(self.visitor, *args) 67 except AttributeError: 68 # NOTE: Obligatory hack to find real attribute errors. 69 if isinstance(node, self.implemented_nodes): 70 raise 71 return self.visitor.default(node, *args) 72 73 implemented_nodes = ( 74 AssAttr, Assign, AssName, AssList, AssTuple, CallFunc, Function, Getattr, 75 Add, Bitand, Bitor, Bitxor, Div, FloorDiv, Invert, LeftShift, Mod, Mul, 76 Power, RightShift, Sub, UnaryAdd, UnarySub 77 ) 78 79 # Deduction-related methods. 80 81 def provides_constant_result(self, value): 82 83 "Return whether 'value' provides a constant result." 84 85 return isinstance(value, (Const, Constant)) 86 87 def provides_self_access(self, expr, unit): 88 89 """ 90 Return whether the 'expr' in the given 'unit' provides a self-based 91 attribute access. 92 """ 93 94 attr_value = self.get_attribute_and_value(expr) 95 96 if attr_value: 97 target, value = attr_value 98 99 return target and target.name == "self" and target.parent is unit and \ 100 unit.is_method() 101 102 return False 103 104 def possible_attributes_from_annotation(self, expr, attr, attrname): 105 106 """ 107 Return (attribute, value) details provided by the 'expr' or 'attr' 108 annotations on a node for an access involving 'attrname'. 109 """ 110 111 attr_value = self.get_attribute_and_value(attr) 112 113 if attr_value: 114 return [attr_value] 115 116 attrs = set() 117 118 if expr: 119 120 # Permitting multiple expression types if they provide the 121 # attribute. 122 123 if isinstance(expr, BaseAttr): 124 exprs = expr.get_values() 125 else: 126 exprs = [expr] 127 128 # For each expression value try and get a concrete attribute. 129 130 for _expr in exprs: 131 if isinstance(_expr, Instance): 132 continue 133 134 found_attr = _expr.all_attributes().get(attrname) 135 136 # Where an attribute can be obtained, record its 137 # details. 138 139 if found_attr: 140 attrs.add((found_attr, found_attr.get_value())) 141 142 return attrs 143 144 def possible_accessor_types_from_usage(self, node, defining_users=1): 145 146 """ 147 Return a set of (target name, static) tuples from an investigation of 148 attribute usage observations stored on the given 'node'. 149 150 If 'defining_users' is set to a false value, attempt to get the type 151 names specifically applicable to the node, rather than retrieving more 152 general definition-based type observations. 153 """ 154 155 target_names = set() 156 157 if node._attrusers: 158 159 # Visit each attribute user. 160 161 for user in node._attrusers: 162 163 # Since users such as branches may not provide type information, 164 # attempt to find defining users. 165 166 if defining_users: 167 for def_user in user._attrdefs or [user]: 168 for target_name, is_static in def_user._attrtypes.get(node._username, []): 169 target_names.add((target_name, is_static)) 170 else: 171 for target_name, is_static in user._attrspecifictypes.get(node._username, []): 172 target_names.add((target_name, is_static)) 173 174 return target_names 175 176 def possible_accessors_from_usage(self, node, defining_users=1): 177 178 """ 179 Return possible accessors from the usage recorded on the given 'node'. 180 181 If 'defining_users' is set to a false value, attempt to get the type 182 names specifically applicable to the node, rather than retrieving more 183 general definition-based type observations. 184 """ 185 186 target_names = self.possible_accessor_types_from_usage(node, defining_users) 187 return self.get_targets_from_type_names(target_names) 188 189 def possible_accessors_for_attribute(self, attrname): 190 191 "Return possible accessors given the single 'attrname'." 192 193 targets = set() 194 195 for target_name in self.objtable.any_possible_objects([attrname]): 196 targets.add(self.objtable.get_object(target_name)) 197 198 return targets 199 200 def get_targets_from_type_names(self, target_names): 201 202 """ 203 Given a collection of 'target_names' of the form (name, is_static), 204 return a set of types for the 'name' part of each tuple. 205 """ 206 207 targets = set() 208 209 if target_names: 210 for target_name, is_static in target_names: 211 targets.add(self.objtable.get_object(target_name)) 212 213 return targets 214 215 # Visitor methods. 216 217 def _visitUnit(self, node): 218 219 """ 220 Track entry into program units in order to support various attribute 221 access operations. 222 """ 223 224 self.units.append(node.unit) 225 self.dispatch(node.node) 226 self.units.pop() 227 228 visitModule = _visitUnit 229 230 def visitClass(self, node): 231 232 "Optionally visit a class, depending on whether it is used." 233 234 if not used_by_unit(node): 235 return 236 self._visitUnit(node) 237 238 def visitFunction(self, node): 239 240 "Optionally visit a function, depending on whether it is used." 241 242 if not used_by_unit(node): 243 return 244 245 self.units.append(node.unit) 246 self.dispatch(node.code) 247 self.units.pop() 248 249 node._guard_types = {} 250 node._guards = {} 251 252 self._visitParameters(node, node.unit.positional_names) 253 254 def _visitParameters(self, node, parameters): 255 for name in parameters: 256 if isinstance(name, tuple): 257 self._visitParameters(node, name) 258 else: 259 # NOTE: No _values usage here because it is mostly useless information, except perhaps for defaults. 260 types = self.get_targets_from_type_names(node._attrtypes.get(name)) 261 self._visitGuardForNameDeduced(node, name, types) 262 263 def _visitAttr(self, node): 264 265 """ 266 Perform deductions on attribute accesses, adding annotations to the node 267 that can be used by subsequent activities. 268 """ 269 270 # Remember to permit deductions on the expression node. Here, we may 271 # also obtain a concrete type associated with an instantiation. 272 273 expr_type = self.dispatch(node.expr) 274 if not node._expr or isinstance(node._expr, Instance): 275 node._expr = expr_type 276 277 self._annotateAttr(node, node._expr, node.attrname) 278 279 # Make a summary annotation of the deductions. 280 281 attributes = node._value_deduced and [self.get_attribute_and_value(node._value_deduced)] or \ 282 node._attr_deduced and [self.get_attribute_and_value(node._attr_deduced)] or \ 283 node._attrs_deduced or \ 284 map(self.get_attribute_and_value, node._attrs_deduced_from_specific_usage or []) 285 286 node._access_attrs = attributes 287 288 # Return the _attr annotation for instantiation detection. 289 290 return node._attr 291 292 def _annotateAttr(self, node, target, attrname): 293 294 """ 295 Annotate the access on the given 'node' using the 'target' and 296 'attrname' information. 297 """ 298 299 unit = self.get_unit() 300 301 # The target, on which the access is performed, may influence the effect 302 # on the context. We can only reliably assume that a literal constant is 303 # an instance: all other "instances" may actually be classes in certain 304 # cases. 305 306 instance_target = isinstance(target, TypedInstance) 307 typed_instance_attr = isinstance(target, BaseAttr) and isinstance(target.get_value(), TypedInstance) 308 self_access = self.provides_self_access(target, unit) 309 310 # Attempt to deduce attributes from explicit annotations. 311 312 node._attrs_deduced = attrs = self.possible_attributes_from_annotation(target, node._attr, attrname) 313 314 if len(attrs) == 1: 315 for attr, value in attrs: 316 317 # Constant values can be obtained directly. 318 319 if self.provides_constant_result(value): 320 node._access_type = "constant" 321 node._value_deduced = value 322 return 323 324 # Static attributes can be obtained via their parent. 325 326 if attr.is_static_attribute(): 327 node._access_type = "static" 328 node._attr_deduced = attr 329 node._set_context = instance_target and "set" or None 330 return 331 332 # If a reliable target was originally specified, any usable attributes 333 # should have been detected above, and any attributes deduced by other 334 # means will not be compatible with the target. Thus, the nature of the 335 # target is investigated: it must be an inspectable namespace or be an 336 # attribute only providing such namespaces; otherwise, it is possible 337 # that deduced attributes might be appropriate. 338 339 if target and ( 340 isinstance(target, (Class, Module)) or 341 isinstance(target, BaseAttr) and not [v for v in target.get_values() if not isinstance(v, (Class, Module))] 342 ): 343 node._access_type = "impossible" 344 return 345 346 # Attributes of self, which is by definition an instance, or typed 347 # instances, which act somewhat like self in that their properties 348 # should be known. 349 350 if instance_target or typed_instance_attr or self_access: 351 352 if instance_target: 353 value = target 354 elif typed_instance_attr: 355 value = target.get_value() 356 357 # Find the class of the instance. 358 359 if instance_target or typed_instance_attr: 360 if isinstance(value, Const): 361 cls = get_constant_class(value.get_class_name()) 362 else: 363 cls = value.cls 364 else: 365 cls = unit.parent 366 367 # Find instance attributes. 368 369 attr = cls.instance_attributes().get(attrname) 370 371 # Where self is involved, descendants can also provide attributes. 372 373 attrs = self_access and filter(None, [desc.instance_attributes().get(attrname) for desc in cls.descendants]) or [] 374 375 # A "leaf" class whose instances provide an attribute. 376 377 if attr and not attrs: 378 node._access_type = "instance" 379 node._attr_deduced = attr 380 return 381 382 # A class where instances of subclasses may provide an attribute. 383 384 elif attrs and self_access: 385 if attr: 386 attrs.append(attr) 387 388 node._attrs_deduced = [(a, a.get_value()) for a in attrs] 389 390 # The instances may provide the attribute at the same position. 391 392 positions = set([a.position for a in attrs]) 393 if len(positions) == 1: 394 for position in positions: 395 node._access_type = "positioned" 396 node._position_deduced = position 397 return 398 399 # Otherwise, accessing the attributes is more work. 400 401 node._access_type = "instance" 402 return 403 404 # Find class attributes. 405 # The context will be overridden for compatible class attributes 406 # only. 407 408 attr = cls.all_class_attributes().get(attrname) 409 410 if attr: 411 412 # Constant attributes. 413 414 if attr.is_strict_constant(): 415 if self.provides_constant_result(attr.get_value()): 416 node._access_type = "constant" 417 node._value_deduced = attr.get_value() 418 node._set_context = "set" 419 return 420 421 # Compatible class attributes. 422 423 if attr.defined_within_hierarchy(): 424 node._access_type = "static" 425 node._attr_deduced = attr 426 node._set_context = "set" 427 return 428 429 # Incompatible class attributes. 430 431 elif attr.defined_outside_hierarchy(): 432 node._access_type = "static" 433 node._attr_deduced = attr 434 return 435 436 # Unknown or mixed compatibility. 437 438 node._access_type = "static" 439 node._attr_deduced = attr 440 node._set_context = "cond" 441 return 442 443 # Usage observations, both specific to this node's region of the program 444 # and also applicable to the lifespan of the affected name. 445 446 specific_targets = self.possible_accessors_from_usage(node, defining_users=0) 447 targets = self.possible_accessors_from_usage(node, defining_users=1) 448 449 # Record whether types were already deduced. If not, get types using 450 # only this attribute. 451 452 if not specific_targets or not targets: 453 attribute_targets = self.possible_accessors_for_attribute(attrname) 454 if not specific_targets: 455 specific_targets = attribute_targets 456 if not targets: 457 targets = attribute_targets 458 459 # Get the attributes from the deduced targets. 460 461 node._attrs_deduced_from_specific_usage = self.get_attributes(specific_targets, attrname) 462 node._attrs_deduced_from_usage = attrs = self.get_attributes(targets, attrname) 463 464 # Generate optimisations where only a single attribute applies. 465 466 if attrs and len(attrs) == 1: 467 for attr in attrs: 468 469 # Static attributes, but potentially non-static targets. 470 471 if attr.is_static_attribute(): 472 473 # Static attributes may be accompanied by a different context 474 # depending on the accessor. 475 # NOTE: Should determine whether the context is always replaced. 476 477 node._access_type = "static" 478 node._attr_deduced = attr 479 node._set_context = instance_target and "set" or "cond" 480 return 481 482 # Non-static attributes. 483 484 node._access_type = "instance" 485 node._attr_deduced = attr 486 return 487 488 # Test for compatible attribute positioning. 489 490 elif attrs: 491 positions = set([(attr.is_static_attribute(), attr.position) for attr in attrs]) 492 493 # Permit a position-based access only on non-static attributes since 494 # access to static attributes may happen via instances and thus not 495 # be relative to the accessor but to its parent. 496 497 if len(positions) == 1: 498 for position in positions: 499 if not position[0]: 500 node._access_type = "positioned" 501 node._position_deduced = position[0] 502 return 503 504 # With no usable deductions, generate a table-based access. 505 506 node._access_type = "unknown" 507 node._set_context = "cond" 508 509 visitAssAttr = visitGetattr = _visitAttr 510 511 def visitAssign(self, node): 512 self.expr = self.dispatch(node.expr) 513 for n in node.nodes: 514 self.dispatch(n) 515 516 def visitAssList(self, node): 517 expr = self.expr 518 self.expr = make_instance() 519 for n in node.nodes: 520 self.dispatch(n) 521 self.expr = expr 522 523 visitAssTuple = visitAssList 524 525 def visitAssName(self, node): 526 if self.expr: 527 if isinstance(self.expr, BaseAttr): 528 expr = self.expr.get_value() 529 elif isinstance(self.expr, TypedInstance): 530 expr = self.expr 531 else: 532 self._visitGuard(node) 533 return 534 else: 535 self._visitGuard(node) 536 return 537 538 attr = node._values and node._values.get(node.name) or None 539 540 # Need to replace any uncertain value with a concrete value. 541 542 if attr: 543 if isinstance(attr, BaseAttr): 544 value = attr.get_value() 545 else: 546 value = attr 547 548 if value and isinstance(value, Instance) and not isinstance(value, TypedInstance): 549 node._values[node.name] = expr or make_instance() 550 551 self._visitGuard(node) 552 553 def _visitGuard(self, node): 554 node._guard_types = {} 555 node._guards = {} 556 self._visitGuardForName(node, node.name) 557 558 def _visitGuardForName(self, node, name): 559 560 "Make an annotation stating the acceptable types for a name." 561 562 # Need to check any concrete value against deductions. 563 # Where no local observations exist, no guard can usefully be asserted. 564 565 if not node._attrtypes and not node._values: 566 return 567 568 types = self.get_targets_from_type_names(node._attrtypes.get(name)) 569 value = node._values.get(name) 570 571 if isinstance(value, BaseAttr): 572 values = value.get_values() 573 else: 574 values = [value] 575 576 # Obtain values with identifiable types. 577 578 typed_values = set() 579 580 for v in values: 581 if isinstance(v, Instance): 582 if not isinstance(v, TypedInstance): 583 return 584 typed_values.add(v.cls) 585 else: 586 typed_values.add(v) 587 588 # Where a concrete type conflicts with deductions, the usage of 589 # attributes cannot be supported and is thus impossible. 590 591 if typed_values: 592 if types and not typed_values.intersection(types): 593 node._guard_types[name] = "impossible" 594 else: 595 node._guard_types[name] = len(typed_values) == 1 and "single" or "multiple" 596 node._guards[name] = typed_values 597 598 # Where no concrete type is known, usage must be checked. 599 600 elif types: 601 self._visitGuardForNameDeduced(node, name, types) 602 603 # Where no deductions are made, no guards are needed. 604 605 def _visitGuardForNameDeduced(self, node, name, types): 606 if not types: 607 return 608 if len(types) == 1: 609 node._guard_types[name] = "single" 610 else: 611 node._guard_types[name] = "multiple" 612 node._guards[name] = types 613 614 def visitCallFunc(self, node): 615 616 "Identify any concrete types involved with instantiation." 617 618 for n in node.getChildNodes()[1:]: # ignore node.node 619 self.dispatch(n) 620 621 # Determine whether the target of the invocation refers to a class. 622 623 attr = self.dispatch(node.node) 624 625 if attr: 626 if not isinstance(attr, (Instance, UnresolvedName)): 627 value = attr.get_value() 628 if value and isinstance(value, Class): 629 return TypedInstance(value) 630 631 def _visitOperator(self, node): 632 633 "Annotate operators with function information." 634 635 self._annotateAttr(node, node._module, node._attr.name) 636 637 visitAdd = \ 638 visitBitand = \ 639 visitBitor = \ 640 visitBitxor = \ 641 visitDiv = \ 642 visitFloorDiv = \ 643 visitInvert = \ 644 visitLeftShift = \ 645 visitMod = \ 646 visitMul = \ 647 visitPower = \ 648 visitRightShift = \ 649 visitSub = \ 650 visitUnaryAdd = \ 651 visitUnarySub = _visitOperator 652 653 # Convenience functions. 654 655 def deduce(program): 656 for module in program.get_importer().get_modules(): 657 DeducedSource(module, program).deduce() 658 659 # vim: tabstop=4 expandtab shiftwidth=4