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 Const, 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 129 # attribute. 130 131 for expr in exprs: 132 found_attr = expr.all_attributes().get(attrname) 133 134 # Where an attribute can be obtained, record its 135 # details. 136 137 if found_attr: 138 attrs.add((found_attr, found_attr.get_value())) 139 140 return attrs 141 142 def possible_accessor_types_from_usage(self, node, defining_users=1): 143 144 """ 145 Return a set of (target name, static) tuples from an investigation of 146 attribute usage observations stored on the given 'node'. 147 148 If 'defining_users' is set to a false value, attempt to get the type 149 names specifically applicable to the node, rather than retrieving more 150 general definition-based type observations. 151 """ 152 153 target_names = set() 154 155 if node._attrusers: 156 157 # Visit each attribute user. 158 159 for user in node._attrusers: 160 161 # Since users such as branches may not provide type information, 162 # attempt to find defining users. 163 164 if defining_users: 165 for def_user in user._attrdefs or [user]: 166 for target_name, is_static in def_user._attrtypes.get(node._username, []): 167 target_names.add((target_name, is_static)) 168 else: 169 for target_name, is_static in user._attrspecifictypes.get(node._username, []): 170 target_names.add((target_name, is_static)) 171 172 return target_names 173 174 def possible_accessors_from_usage(self, node, defining_users=1): 175 176 """ 177 Return possible accessors from the usage recorded on the given 'node'. 178 179 If 'defining_users' is set to a false value, attempt to get the type 180 names specifically applicable to the node, rather than retrieving more 181 general definition-based type observations. 182 """ 183 184 target_names = self.possible_accessor_types_from_usage(node, defining_users) 185 return self.get_targets_from_type_names(target_names) 186 187 def possible_accessors_for_attribute(self, attrname): 188 189 "Return possible accessors given the single 'attrname'." 190 191 targets = set() 192 193 for target_name in self.objtable.any_possible_objects([attrname]): 194 targets.add(self.objtable.get_object(target_name)) 195 196 return targets 197 198 def get_targets_from_type_names(self, target_names): 199 200 """ 201 Given a collection of 'target_names' of the form (name, is_static), 202 return a set of types for the 'name' part of each tuple. 203 """ 204 205 targets = set() 206 207 if target_names: 208 for target_name, is_static in target_names: 209 targets.add(self.objtable.get_object(target_name)) 210 211 return targets 212 213 # Visitor methods. 214 215 def _visitUnit(self, node): 216 217 """ 218 Track entry into program units in order to support various attribute 219 access operations. 220 """ 221 222 self.units.append(node.unit) 223 self.dispatch(node.node) 224 self.units.pop() 225 226 visitModule = _visitUnit 227 228 def visitClass(self, node): 229 230 "Optionally visit a class, depending on whether it is used." 231 232 if not used_by_unit(node): 233 return 234 self._visitUnit(node) 235 236 def visitFunction(self, node): 237 238 "Optionally visit a function, depending on whether it is used." 239 240 if not used_by_unit(node): 241 return 242 243 self.units.append(node.unit) 244 self.dispatch(node.code) 245 self.units.pop() 246 247 node._guard_types = {} 248 node._guards = {} 249 250 self._visitParameters(node, node.unit.positional_names) 251 252 def _visitParameters(self, node, parameters): 253 for name in parameters: 254 if isinstance(name, tuple): 255 self._visitParameters(node, name) 256 else: 257 # NOTE: No _values usage here because it is mostly useless information, except perhaps for defaults. 258 types = self.get_targets_from_type_names(node._attrtypes.get(name)) 259 self._visitGuardForNameDeduced(node, name, types) 260 261 def _visitAttr(self, node): 262 263 """ 264 Perform deductions on attribute accesses, adding annotations to the node 265 that can be used by subsequent activities. 266 """ 267 268 # Remember to permit deductions on the expression node. Here, we may 269 # also obtain a concrete type associated with an instantiation. 270 271 expr_type = self.dispatch(node.expr) 272 if not node._expr or isinstance(node._expr, Instance): 273 node._expr = expr_type 274 275 # The target, on which the access is performed, may influence the effect 276 # on the context. We can only reliably assume that a literal constant is 277 # an instance: all other "instances" may actually be classes in certain 278 # cases. 279 280 self._annotateAttr(node, node._expr, node.attrname) 281 282 def _annotateAttr(self, node, target, attrname): 283 284 """ 285 Annotate the access on the given 'node' using the 'target' and 286 'attrname' information. 287 """ 288 289 unit = self.get_unit() 290 291 instance_target = isinstance(target, TypedInstance) 292 typed_instance_attr = isinstance(target, BaseAttr) and isinstance(target.get_value(), TypedInstance) 293 self_access = self.provides_self_access(target, unit) 294 295 # Attempt to deduce attributes from explicit annotations. 296 297 node._attrs_deduced = attrs = self.possible_attributes_from_annotation(target, node._attr, attrname) 298 299 if len(attrs) == 1: 300 for attr, value in attrs: 301 302 # Constant values can be obtained directly. 303 304 if self.provides_constant_result(value): 305 node._access_type = "constant" 306 node._value_deduced = value 307 return 308 309 # Static attributes can be obtained via their parent. 310 311 if attr.is_static_attribute(): 312 node._access_type = "static" 313 node._attr_deduced = attr 314 node._set_context = instance_target and "set" or None 315 return 316 317 # If a reliable target was originally specified, any usable attributes 318 # should have been detected above, and any attributes deduced by other 319 # means will not be compatible with the target. Thus, the nature of the 320 # target is investigated: it must be an inspectable namespace or be an 321 # attribute only providing such namespaces; otherwise, it is possible 322 # that deduced attributes might be appropriate. 323 324 if target and ( 325 isinstance(target, (Class, Module)) or 326 isinstance(target, BaseAttr) and not [v for v in target.get_values() if not isinstance(v, (Class, Module))] 327 ): 328 node._access_type = "impossible" 329 return 330 331 # Attributes of self, which is by definition an instance, or typed 332 # instances, which act somewhat like self in that their properties 333 # should be known. 334 335 if instance_target or typed_instance_attr or self_access: 336 337 if instance_target: 338 value = target 339 elif typed_instance_attr: 340 value = target.get_value() 341 342 # Find the class of the instance. 343 344 if instance_target or typed_instance_attr: 345 if isinstance(value, Const): 346 cls = get_constant_class(value.get_class_name()) 347 else: 348 cls = value.cls 349 else: 350 cls = unit.parent 351 352 # Find instance attributes. 353 354 attr = cls.instance_attributes().get(attrname) 355 356 # Where self is involved, descendants can also provide attributes. 357 358 attrs = self_access and filter(None, [desc.instance_attributes().get(attrname) for desc in cls.descendants]) or [] 359 360 # A "leaf" class whose instances provide an attribute. 361 362 if attr and not attrs: 363 node._access_type = "instance" 364 node._attr_deduced = attr 365 return 366 367 # A class where instances of subclasses may provide an attribute. 368 369 elif attrs and self_access: 370 if attr: 371 attrs.append(attr) 372 373 node._attrs_deduced = [(a, a.get_value()) for a in attrs] 374 375 # The instances may provide the attribute at the same position. 376 377 positions = set([a.position for a in attrs]) 378 if len(positions) == 1: 379 for position in positions: 380 node._access_type = "positioned" 381 node._position_deduced = position 382 return 383 384 # Otherwise, accessing the attributes is more work. 385 386 node._access_type = "instance" 387 return 388 389 # Find class attributes. 390 # The context will be overridden for compatible class attributes 391 # only. 392 393 attr = cls.all_class_attributes().get(attrname) 394 395 if attr: 396 397 # Constant attributes. 398 399 if attr.is_strict_constant(): 400 if self.provides_constant_result(attr.get_value()): 401 node._access_type = "constant" 402 node._value_deduced = attr.get_value() 403 node._set_context = "set" 404 return 405 406 # Compatible class attributes. 407 408 if attr.defined_within_hierarchy(): 409 node._access_type = "static" 410 node._attr_deduced = attr 411 node._set_context = "set" 412 return 413 414 # Incompatible class attributes. 415 416 elif attr.defined_outside_hierarchy(): 417 node._access_type = "static" 418 node._attr_deduced = attr 419 return 420 421 # Unknown or mixed compatibility. 422 423 node._access_type = "static" 424 node._attr_deduced = attr 425 node._set_context = "cond" 426 return 427 428 # Usage observations, both specific to this node's region of the program 429 # and also applicable to the lifespan of the affected name. 430 431 specific_targets = self.possible_accessors_from_usage(node, defining_users=0) 432 targets = self.possible_accessors_from_usage(node, defining_users=1) 433 434 # Record whether types were already deduced. If not, get types using 435 # only this attribute. 436 437 if not specific_targets or not targets: 438 attribute_targets = self.possible_accessors_for_attribute(attrname) 439 if not specific_targets: 440 specific_targets = attribute_targets 441 if not targets: 442 targets = attribute_targets 443 444 # Get the attributes from the deduced targets. 445 446 node._attrs_deduced_from_specific_usage = self.get_attributes(specific_targets, attrname) 447 node._attrs_deduced_from_usage = attrs = self.get_attributes(targets, attrname) 448 449 # Generate optimisations where only a single attribute applies. 450 451 if attrs and len(attrs) == 1: 452 for attr in attrs: 453 454 # Static attributes, but potentially non-static targets. 455 456 if attr.is_static_attribute(): 457 458 # Static attributes may be accompanied by a different context 459 # depending on the accessor. 460 # NOTE: Should determine whether the context is always replaced. 461 462 node._access_type = "static" 463 node._attr_deduced = attr 464 node._set_context = instance_target and "set" or "cond" 465 return 466 467 # Non-static attributes. 468 469 node._access_type = "instance" 470 node._attr_deduced = attr 471 return 472 473 # Test for compatible attribute positioning. 474 475 elif attrs: 476 positions = set([(attr.is_static_attribute(), attr.position) for attr in attrs]) 477 478 # Permit a position-based access only on non-static attributes since 479 # access to static attributes may happen via instances and thus not 480 # be relative to the accessor but to its parent. 481 482 if len(positions) == 1: 483 for position in positions: 484 if not position[0]: 485 node._access_type = "positioned" 486 node._position_deduced = position[0] 487 return 488 489 # With no usable deductions, generate a table-based access. 490 491 node._access_type = "unknown" 492 node._set_context = "cond" 493 494 visitAssAttr = visitGetattr = _visitAttr 495 496 def visitAssign(self, node): 497 self.expr = self.dispatch(node.expr) 498 for n in node.nodes: 499 self.dispatch(n) 500 501 def visitAssList(self, node): 502 expr = self.expr 503 self.expr = make_instance() 504 for n in node.nodes: 505 self.dispatch(n) 506 self.expr = expr 507 508 visitAssTuple = visitAssList 509 510 def visitAssName(self, node): 511 if self.expr: 512 if isinstance(self.expr, BaseAttr): 513 expr = self.expr.get_value() 514 elif isinstance(self.expr, TypedInstance): 515 expr = self.expr 516 else: 517 self._visitGuard(node) 518 return 519 else: 520 self._visitGuard(node) 521 return 522 523 attr = node._values and node._values.get(node.name) or None 524 525 # Need to replace any uncertain value with a concrete value. 526 527 if attr: 528 if isinstance(attr, BaseAttr): 529 value = attr.get_value() 530 else: 531 value = attr 532 533 if value and isinstance(value, Instance) and not isinstance(value, TypedInstance): 534 node._values[node.name] = expr 535 536 self._visitGuard(node) 537 538 def _visitGuard(self, node): 539 node._guard_types = {} 540 node._guards = {} 541 self._visitGuardForName(node, node.name) 542 543 def _visitGuardForName(self, node, name): 544 545 "Make an annotation stating the acceptable types for a name." 546 547 # Need to check any concrete value against deductions. 548 549 types = self.get_targets_from_type_names(node._attrtypes.get(name)) 550 value = node._values.get(name) 551 552 # Where a concrete type conflicts with deductions, the usage of 553 # attributes cannot be supported and is thus impossible. 554 555 if value: 556 if types and value not in types: 557 node._guard_types[name] = "impossible" 558 else: 559 node._guard_types[name] = "single" 560 node._guards[name] = set([value]) 561 562 # Where no concrete type is known, usage must be checked. 563 564 elif types: 565 self._visitGuardForNameDeduced(node, name, types) 566 567 # Where no deductions are made, no guards are needed. 568 569 def _visitGuardForNameDeduced(self, node, name, types): 570 if not types: 571 return 572 if len(types) == 1: 573 node._guard_types[name] = "single" 574 else: 575 node._guard_types[name] = "multiple" 576 node._guards[name] = types 577 578 def visitCallFunc(self, node): 579 580 "Identify any concrete types involved with instantiation." 581 582 for n in node.getChildNodes(): 583 self.dispatch(n) 584 585 # Determine whether the target of the invocation refers to a class. 586 587 attr = node.node._attr 588 589 if attr and not isinstance(attr, Instance): 590 value = attr.get_value() 591 if value and isinstance(value, Class): 592 return TypedInstance(value) 593 594 def _visitOperator(self, node): 595 596 "Annotate operators with function information." 597 598 self._annotateAttr(node, node._module, node._attr.name) 599 600 visitAdd = \ 601 visitBitand = \ 602 visitBitor = \ 603 visitBitxor = \ 604 visitDiv = \ 605 visitFloorDiv = \ 606 visitInvert = \ 607 visitLeftShift = \ 608 visitMod = \ 609 visitMul = \ 610 visitPower = \ 611 visitRightShift = \ 612 visitSub = \ 613 visitUnaryAdd = \ 614 visitUnarySub = _visitOperator 615 616 # Convenience functions. 617 618 def deduce(program): 619 for module in program.get_importer().get_modules(): 620 DeducedSource(module, program).deduce() 621 622 # vim: tabstop=4 expandtab shiftwidth=4