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 self._annotateAttr(node, node._expr, node.attrname) 276 277 # Make a summary annotation of the deductions. 278 279 attributes = node._value_deduced and [self.get_attribute_and_value(node._value_deduced)] or \ 280 node._attr_deduced and [self.get_attribute_and_value(node._attr_deduced)] or \ 281 node._attrs_deduced or \ 282 map(self.get_attribute_and_value, node._attrs_deduced_from_specific_usage or []) 283 284 node._access_attrs = attributes 285 286 def _annotateAttr(self, node, target, attrname): 287 288 """ 289 Annotate the access on the given 'node' using the 'target' and 290 'attrname' information. 291 """ 292 293 unit = self.get_unit() 294 295 # The target, on which the access is performed, may influence the effect 296 # on the context. We can only reliably assume that a literal constant is 297 # an instance: all other "instances" may actually be classes in certain 298 # cases. 299 300 instance_target = isinstance(target, TypedInstance) 301 typed_instance_attr = isinstance(target, BaseAttr) and isinstance(target.get_value(), TypedInstance) 302 self_access = self.provides_self_access(target, unit) 303 304 # Attempt to deduce attributes from explicit annotations. 305 306 node._attrs_deduced = attrs = self.possible_attributes_from_annotation(target, node._attr, attrname) 307 308 if len(attrs) == 1: 309 for attr, value in attrs: 310 311 # Constant values can be obtained directly. 312 313 if self.provides_constant_result(value): 314 node._access_type = "constant" 315 node._value_deduced = value 316 return 317 318 # Static attributes can be obtained via their parent. 319 320 if attr.is_static_attribute(): 321 node._access_type = "static" 322 node._attr_deduced = attr 323 node._set_context = instance_target and "set" or None 324 return 325 326 # If a reliable target was originally specified, any usable attributes 327 # should have been detected above, and any attributes deduced by other 328 # means will not be compatible with the target. Thus, the nature of the 329 # target is investigated: it must be an inspectable namespace or be an 330 # attribute only providing such namespaces; otherwise, it is possible 331 # that deduced attributes might be appropriate. 332 333 if target and ( 334 isinstance(target, (Class, Module)) or 335 isinstance(target, BaseAttr) and not [v for v in target.get_values() if not isinstance(v, (Class, Module))] 336 ): 337 node._access_type = "impossible" 338 return 339 340 # Attributes of self, which is by definition an instance, or typed 341 # instances, which act somewhat like self in that their properties 342 # should be known. 343 344 if instance_target or typed_instance_attr or self_access: 345 346 if instance_target: 347 value = target 348 elif typed_instance_attr: 349 value = target.get_value() 350 351 # Find the class of the instance. 352 353 if instance_target or typed_instance_attr: 354 if isinstance(value, Const): 355 cls = get_constant_class(value.get_class_name()) 356 else: 357 cls = value.cls 358 else: 359 cls = unit.parent 360 361 # Find instance attributes. 362 363 attr = cls.instance_attributes().get(attrname) 364 365 # Where self is involved, descendants can also provide attributes. 366 367 attrs = self_access and filter(None, [desc.instance_attributes().get(attrname) for desc in cls.descendants]) or [] 368 369 # A "leaf" class whose instances provide an attribute. 370 371 if attr and not attrs: 372 node._access_type = "instance" 373 node._attr_deduced = attr 374 return 375 376 # A class where instances of subclasses may provide an attribute. 377 378 elif attrs and self_access: 379 if attr: 380 attrs.append(attr) 381 382 node._attrs_deduced = [(a, a.get_value()) for a in attrs] 383 384 # The instances may provide the attribute at the same position. 385 386 positions = set([a.position for a in attrs]) 387 if len(positions) == 1: 388 for position in positions: 389 node._access_type = "positioned" 390 node._position_deduced = position 391 return 392 393 # Otherwise, accessing the attributes is more work. 394 395 node._access_type = "instance" 396 return 397 398 # Find class attributes. 399 # The context will be overridden for compatible class attributes 400 # only. 401 402 attr = cls.all_class_attributes().get(attrname) 403 404 if attr: 405 406 # Constant attributes. 407 408 if attr.is_strict_constant(): 409 if self.provides_constant_result(attr.get_value()): 410 node._access_type = "constant" 411 node._value_deduced = attr.get_value() 412 node._set_context = "set" 413 return 414 415 # Compatible class attributes. 416 417 if attr.defined_within_hierarchy(): 418 node._access_type = "static" 419 node._attr_deduced = attr 420 node._set_context = "set" 421 return 422 423 # Incompatible class attributes. 424 425 elif attr.defined_outside_hierarchy(): 426 node._access_type = "static" 427 node._attr_deduced = attr 428 return 429 430 # Unknown or mixed compatibility. 431 432 node._access_type = "static" 433 node._attr_deduced = attr 434 node._set_context = "cond" 435 return 436 437 # Usage observations, both specific to this node's region of the program 438 # and also applicable to the lifespan of the affected name. 439 440 specific_targets = self.possible_accessors_from_usage(node, defining_users=0) 441 targets = self.possible_accessors_from_usage(node, defining_users=1) 442 443 # Record whether types were already deduced. If not, get types using 444 # only this attribute. 445 446 if not specific_targets or not targets: 447 attribute_targets = self.possible_accessors_for_attribute(attrname) 448 if not specific_targets: 449 specific_targets = attribute_targets 450 if not targets: 451 targets = attribute_targets 452 453 # Get the attributes from the deduced targets. 454 455 node._attrs_deduced_from_specific_usage = self.get_attributes(specific_targets, attrname) 456 node._attrs_deduced_from_usage = attrs = self.get_attributes(targets, attrname) 457 458 # Generate optimisations where only a single attribute applies. 459 460 if attrs and len(attrs) == 1: 461 for attr in attrs: 462 463 # Static attributes, but potentially non-static targets. 464 465 if attr.is_static_attribute(): 466 467 # Static attributes may be accompanied by a different context 468 # depending on the accessor. 469 # NOTE: Should determine whether the context is always replaced. 470 471 node._access_type = "static" 472 node._attr_deduced = attr 473 node._set_context = instance_target and "set" or "cond" 474 return 475 476 # Non-static attributes. 477 478 node._access_type = "instance" 479 node._attr_deduced = attr 480 return 481 482 # Test for compatible attribute positioning. 483 484 elif attrs: 485 positions = set([(attr.is_static_attribute(), attr.position) for attr in attrs]) 486 487 # Permit a position-based access only on non-static attributes since 488 # access to static attributes may happen via instances and thus not 489 # be relative to the accessor but to its parent. 490 491 if len(positions) == 1: 492 for position in positions: 493 if not position[0]: 494 node._access_type = "positioned" 495 node._position_deduced = position[0] 496 return 497 498 # With no usable deductions, generate a table-based access. 499 500 node._access_type = "unknown" 501 node._set_context = "cond" 502 503 visitAssAttr = visitGetattr = _visitAttr 504 505 def visitAssign(self, node): 506 self.expr = self.dispatch(node.expr) 507 for n in node.nodes: 508 self.dispatch(n) 509 510 def visitAssList(self, node): 511 expr = self.expr 512 self.expr = make_instance() 513 for n in node.nodes: 514 self.dispatch(n) 515 self.expr = expr 516 517 visitAssTuple = visitAssList 518 519 def visitAssName(self, node): 520 if self.expr: 521 if isinstance(self.expr, BaseAttr): 522 expr = self.expr.get_value() 523 elif isinstance(self.expr, TypedInstance): 524 expr = self.expr 525 else: 526 self._visitGuard(node) 527 return 528 else: 529 self._visitGuard(node) 530 return 531 532 attr = node._values and node._values.get(node.name) or None 533 534 # Need to replace any uncertain value with a concrete value. 535 536 if attr: 537 if isinstance(attr, BaseAttr): 538 value = attr.get_value() 539 else: 540 value = attr 541 542 if value and isinstance(value, Instance) and not isinstance(value, TypedInstance): 543 node._values[node.name] = expr 544 545 self._visitGuard(node) 546 547 def _visitGuard(self, node): 548 node._guard_types = {} 549 node._guards = {} 550 self._visitGuardForName(node, node.name) 551 552 def _visitGuardForName(self, node, name): 553 554 "Make an annotation stating the acceptable types for a name." 555 556 # Need to check any concrete value against deductions. 557 558 types = self.get_targets_from_type_names(node._attrtypes.get(name)) 559 value = node._values.get(name) 560 561 # Where a concrete type conflicts with deductions, the usage of 562 # attributes cannot be supported and is thus impossible. 563 564 if value: 565 if types and value not in types: 566 node._guard_types[name] = "impossible" 567 else: 568 node._guard_types[name] = "single" 569 node._guards[name] = set([value]) 570 571 # Where no concrete type is known, usage must be checked. 572 573 elif types: 574 self._visitGuardForNameDeduced(node, name, types) 575 576 # Where no deductions are made, no guards are needed. 577 578 def _visitGuardForNameDeduced(self, node, name, types): 579 if not types: 580 return 581 if len(types) == 1: 582 node._guard_types[name] = "single" 583 else: 584 node._guard_types[name] = "multiple" 585 node._guards[name] = types 586 587 def visitCallFunc(self, node): 588 589 "Identify any concrete types involved with instantiation." 590 591 for n in node.getChildNodes(): 592 self.dispatch(n) 593 594 # Determine whether the target of the invocation refers to a class. 595 596 attr = node.node._attr 597 598 if attr and not isinstance(attr, Instance): 599 value = attr.get_value() 600 if value and isinstance(value, Class): 601 return TypedInstance(value) 602 603 def _visitOperator(self, node): 604 605 "Annotate operators with function information." 606 607 self._annotateAttr(node, node._module, node._attr.name) 608 609 visitAdd = \ 610 visitBitand = \ 611 visitBitor = \ 612 visitBitxor = \ 613 visitDiv = \ 614 visitFloorDiv = \ 615 visitInvert = \ 616 visitLeftShift = \ 617 visitMod = \ 618 visitMul = \ 619 visitPower = \ 620 visitRightShift = \ 621 visitSub = \ 622 visitUnaryAdd = \ 623 visitUnarySub = _visitOperator 624 625 # Convenience functions. 626 627 def deduce(program): 628 for module in program.get_importer().get_modules(): 629 DeducedSource(module, program).deduce() 630 631 # vim: tabstop=4 expandtab shiftwidth=4