1 #!/usr/bin/env python 2 3 """ 4 Perform deductions on an inspected program. 5 6 Copyright (C) 2006, 2007, 2010, 2011, 2012, 2013 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 AssAttr, Getattr, Name 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, 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 def _visitOptionalUnit(self, node): 218 219 "Optionally visit a unit, depending on whether it is used." 220 221 if not used_by_unit(node): 222 return 223 self._visitUnit(node) 224 225 visitModule = _visitUnit 226 visitClass = visitFunction = _visitOptionalUnit 227 228 def _visitAttr(self, node): 229 230 """ 231 Perform deductions on attribute accesses, adding annotations to the node 232 that can be used by subsequent activities. 233 """ 234 235 # Remember to permit deductions on the expression node. Here, we may 236 # also obtain a concrete type associated with an instantiation. 237 238 expr_type = self.dispatch(node.expr) 239 if not node._expr or isinstance(node._expr, Instance): 240 node._expr = expr_type 241 242 # The target, on which the access is performed, may influence the effect 243 # on the context. We can only reliably assume that a literal constant is 244 # an instance: all other "instances" may actually be classes in certain 245 # cases. 246 247 self._annotateAttr(node, node._expr, node.attrname) 248 249 def _annotateAttr(self, node, target, attrname): 250 251 """ 252 Annotate the access on the given 'node' using the 'target' and 253 'attrname' information. 254 """ 255 256 unit = self.get_unit() 257 258 instance_target = isinstance(target, TypedInstance) 259 typed_instance_attr = isinstance(target, BaseAttr) and isinstance(target.get_value(), TypedInstance) 260 self_access = self.provides_self_access(target, unit) 261 262 # Attempt to deduce attributes from explicit annotations. 263 264 node._attrs_deduced = attrs = self.possible_attributes_from_annotation(target, node._attr, attrname) 265 266 if len(attrs) == 1: 267 for attr, value in attrs: 268 269 # Constant values can be obtained directly. 270 271 if self.provides_constant_result(value): 272 node._access_type = "constant" 273 node._value_deduced = value 274 return 275 276 # Static attributes can be obtained via their parent. 277 278 if attr.is_static_attribute(): 279 node._access_type = "static" 280 node._attr_deduced = attr 281 node._set_context = instance_target and "set" or None 282 return 283 284 # If a reliable target was originally specified, any usable attributes 285 # should have been detected above, and any attributes deduced by other 286 # means will not be compatible with the target. Thus, the nature of the 287 # target is investigated: it must be an inspectable namespace or be an 288 # attribute only providing such namespaces; otherwise, it is possible 289 # that deduced attributes might be appropriate. 290 291 if target and ( 292 isinstance(target, (Class, Module)) or 293 isinstance(target, BaseAttr) and not [v for v in target.get_values() if not isinstance(v, (Class, Module))] 294 ): 295 node._access_type = "impossible" 296 return 297 298 # Attributes of self, which is by definition an instance, or typed 299 # instances, which act somewhat like self in that their properties 300 # should be known. 301 302 if instance_target or typed_instance_attr or self_access: 303 304 if instance_target: 305 value = target 306 elif typed_instance_attr: 307 value = target.get_value() 308 309 # Find the class of the instance. 310 311 if instance_target or typed_instance_attr: 312 if isinstance(value, Const): 313 cls = get_constant_class(value.get_class_name()) 314 else: 315 cls = value.cls 316 else: 317 cls = unit.parent 318 319 # Find instance attributes. 320 321 attr = cls.instance_attributes().get(attrname) 322 323 # Where self is involved, descendants can also provide attributes. 324 325 attrs = self_access and filter(None, [desc.instance_attributes().get(attrname) for desc in cls.descendants]) or [] 326 327 # A "leaf" class whose instances provide an attribute. 328 329 if attr and not attrs: 330 node._access_type = "instance" 331 node._attr_deduced = attr 332 return 333 334 # A class where instances of subclasses may provide an attribute. 335 336 elif attrs and self_access: 337 if attr: 338 attrs.append(attr) 339 340 node._attrs_deduced = [(a, a.get_value()) for a in attrs] 341 342 # The instances may provide the attribute at the same position. 343 344 positions = set([a.position for a in attrs]) 345 if len(positions) == 1: 346 for position in positions: 347 node._access_type = "positioned" 348 node._position_deduced = position 349 return 350 351 # Otherwise, accessing the attributes is more work. 352 353 node._access_type = "instance" 354 return 355 356 # Find class attributes. 357 # The context will be overridden for compatible class attributes 358 # only. 359 360 attr = cls.all_class_attributes().get(attrname) 361 362 if attr: 363 364 # Constant attributes. 365 366 if attr.is_strict_constant(): 367 if self.provides_constant_result(attr.get_value()): 368 node._access_type = "constant" 369 node._value_deduced = attr.get_value() 370 node._set_context = "set" 371 return 372 373 # Compatible class attributes. 374 375 if attr.defined_within_hierarchy(): 376 node._access_type = "static" 377 node._attr_deduced = attr 378 node._set_context = "set" 379 return 380 381 # Incompatible class attributes. 382 383 elif attr.defined_outside_hierarchy(): 384 node._access_type = "static" 385 node._attr_deduced = attr 386 return 387 388 # Unknown or mixed compatibility. 389 390 node._access_type = "static" 391 node._attr_deduced = attr 392 node._set_context = "cond" 393 return 394 395 # Usage observations, both specific to this node's region of the program 396 # and also applicable to the lifespan of the affected name. 397 398 specific_targets = self.possible_accessors_from_usage(node, defining_users=0) 399 targets = self.possible_accessors_from_usage(node, defining_users=1) 400 401 # Record whether types were already deduced. If not, get types using 402 # only this attribute. 403 404 if not specific_targets or not targets: 405 attribute_targets = self.possible_accessors_for_attribute(attrname) 406 if not specific_targets: 407 specific_targets = attribute_targets 408 if not targets: 409 targets = attribute_targets 410 411 # Get the attributes from the deduced targets. 412 413 node._attrs_deduced_from_specific_usage = self.get_attributes(specific_targets, attrname) 414 node._attrs_deduced_from_usage = attrs = self.get_attributes(targets, attrname) 415 416 # Generate optimisations where only a single attribute applies. 417 418 if attrs and len(attrs) == 1: 419 for attr in attrs: 420 421 # Static attributes, but potentially non-static targets. 422 423 if attr.is_static_attribute(): 424 425 # Static attributes may be accompanied by a different context 426 # depending on the accessor. 427 # NOTE: Should determine whether the context is always replaced. 428 429 node._access_type = "static" 430 node._attr_deduced = attr 431 node._set_context = instance_target and "set" or "cond" 432 return 433 434 # Non-static attributes. 435 436 node._access_type = "instance" 437 node._attr_deduced = attr 438 return 439 440 # Test for compatible attribute positioning. 441 442 elif attrs: 443 positions = set([(attr.is_static_attribute(), attr.position) for attr in attrs]) 444 445 # Permit a position-based access only on non-static attributes since 446 # access to static attributes may happen via instances and thus not 447 # be relative to the accessor but to its parent. 448 449 if len(positions) == 1: 450 for position in positions: 451 if not position[0]: 452 node._access_type = "positioned" 453 node._position_deduced = position[0] 454 return 455 456 # With no usable deductions, generate a table-based access. 457 458 node._access_type = "unknown" 459 node._set_context = "cond" 460 461 visitAssAttr = visitGetattr = _visitAttr 462 463 def visitAssign(self, node): 464 self.expr = self.dispatch(node.expr) 465 for n in node.nodes: 466 self.dispatch(n) 467 468 def visitAssList(self, node): 469 expr = self.expr 470 self.expr = make_instance() 471 for n in node.nodes: 472 self.dispatch(n) 473 self.expr = expr 474 475 visitAssTuple = visitAssList 476 477 def visitAssName(self, node): 478 if self.expr: 479 if isinstance(self.expr, BaseAttr): 480 expr = self.expr.get_value() 481 elif isinstance(self.expr, TypedInstance): 482 expr = self.expr 483 else: 484 return 485 else: 486 return 487 488 attr = node._values and node._values.get(node.name) or None 489 490 # Need to replace any uncertain value with a concrete value. 491 492 if attr: 493 if isinstance(attr, BaseAttr): 494 value = attr.get_value() 495 else: 496 value = attr 497 498 if value and isinstance(value, Instance) and not isinstance(value, TypedInstance): 499 node._values[node.name] = self.expr 500 501 def visitCallFunc(self, node): 502 503 "Identify any concrete types involved with instantiation." 504 505 for n in node.getChildNodes(): 506 self.dispatch(n) 507 508 # Determine whether the target of the invocation refers to a class. 509 510 attr = node.node._attr 511 512 if attr: 513 value = attr.get_value() 514 if value and isinstance(value, Class): 515 return TypedInstance(value) 516 517 def _visitOperator(self, node): 518 519 "Annotate operators with function information." 520 521 self._annotateAttr(node, node._module, node._attr.name) 522 523 visitAdd = \ 524 visitBitand = \ 525 visitBitor = \ 526 visitBitxor = \ 527 visitDiv = \ 528 visitFloorDiv = \ 529 visitInvert = \ 530 visitLeftShift = \ 531 visitMod = \ 532 visitMul = \ 533 visitPower = \ 534 visitRightShift = \ 535 visitSub = \ 536 visitUnaryAdd = \ 537 visitUnarySub = _visitOperator 538 539 # Convenience functions. 540 541 def deduce(program): 542 for module in program.get_importer().get_modules(): 543 DeducedSource(module, program).deduce() 544 545 # vim: tabstop=4 expandtab shiftwidth=4