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