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.common import * 23 from micropython.data import * 24 from micropython.errors import * 25 26 # Source code classes. 27 28 class DeducedSource(ASTVisitor): 29 30 "A module upon which deductions of code behaviour are made." 31 32 def __init__(self, module, program): 33 self.visitor = self 34 self.module = module 35 self.program = program 36 self.objtable = program.get_object_table() 37 self.units = [] 38 self.expr = None 39 40 def get_unit(self): 41 return self.units[-1] 42 43 def get_module(self): 44 return self.units[0] 45 46 def deduce(self): 47 48 "Process the module, making deductions." 49 50 self.dispatch(self.module.astnode) 51 52 def dispatch(self, node, *args): 53 54 "NOTE: From compiler.visitor.ASTVisitor." 55 56 try: 57 return node.visit(self.visitor, *args) 58 except AttributeError: 59 # NOTE: Obligatory hack to find real attribute errors. 60 if isinstance(node, (Getattr, AssAttr)): 61 raise 62 return self.visitor.default(node, *args) 63 64 def _visitUnit(self, node): 65 66 """ 67 Track entry into program units in order to support various attribute 68 access operations. 69 """ 70 71 self.units.append(node.unit) 72 self.dispatch(node.node) 73 self.units.pop() 74 75 def _visitOptionalUnit(self, node): 76 77 "Optionally visit a unit, depending on whether it is used." 78 79 if not used_by_unit(node): 80 return 81 self._visitUnit(node) 82 83 visitModule = _visitUnit 84 visitClass = visitFunction = _visitOptionalUnit 85 86 def _visitAttr(self, node): 87 88 """ 89 Perform deductions on attribute accesses, adding annotations to the node 90 that can be used by subsequent activities. 91 """ 92 93 # Remember to permit deductions on the expression node. Here, we may 94 # also obtain a concrete type associated with an instantiation. 95 96 expr_type = self.dispatch(node.expr) 97 if not node._expr or isinstance(node._expr, Instance): 98 node._expr = expr_type 99 100 # The target, on which the access is performed, may influence the effect 101 # on the context. We can only reliably assume that a literal constant is 102 # an instance: all other "instances" may actually be classes in certain 103 # cases. 104 105 self._annotateAttr(node, node._expr, node.attrname) 106 107 def _annotateAttr(self, node, target, attrname): 108 109 """ 110 Annotate the access on the given 'node' using the 'target' and 111 'attrname' information. 112 """ 113 114 unit = self.get_unit() 115 116 instance_target = isinstance(target, TypedInstance) 117 typed_instance_attr = isinstance(target, BaseAttr) and isinstance(target.get_value(), TypedInstance) 118 self_access = self.provides_self_access(target, unit) 119 120 # Attempt to deduce attributes from explicit annotations. 121 122 node._attrs_deduced = attrs = self.possible_attributes_from_annotation(target, node._attr, attrname) 123 124 if len(attrs) == 1: 125 for attr, value in attrs: 126 127 # Constant values can be obtained directly. 128 129 if self.provides_constant_result(value): 130 node._access_type = "constant" 131 node._value_deduced = value 132 return 133 134 # Static attributes can be obtained via their parent. 135 136 if attr.is_static_attribute(): 137 node._access_type = "static" 138 node._attr_deduced = attr 139 node._set_context = instance_target and "set" or None 140 return 141 142 # If a reliable target was originally specified, any usable attributes 143 # should have been detected above, and any attributes deduced by other 144 # means will not be compatible with the target. Thus, the nature of the 145 # target is investigated: it must be an inspectable namespace or be an 146 # attribute only providing such namespaces; otherwise, it is possible 147 # that deduced attributes might be appropriate. 148 149 if target and ( 150 isinstance(target, (Class, Module)) or 151 isinstance(target, BaseAttr) and not [v for v in target.get_values() if not isinstance(v, (Class, Module))] 152 ): 153 node._access_type = "impossible" 154 return 155 156 # Attributes of self, which is by definition an instance, or typed 157 # instances, which act somewhat like self in that their properties 158 # should be known. 159 160 if instance_target or typed_instance_attr or self_access: 161 162 if instance_target: 163 value = target 164 elif typed_instance_attr: 165 value = target.get_value() 166 167 # Find the class of the instance. 168 169 if instance_target or typed_instance_attr: 170 if isinstance(value, Const): 171 cls = get_constant_class(value.get_class_name()) 172 else: 173 cls = value.cls 174 else: 175 cls = unit.parent 176 177 # Find instance attributes. 178 179 attr = cls.instance_attributes().get(attrname) 180 181 # Where self is involved, descendants can also provide attributes. 182 183 attrs = self_access and filter(None, [desc.instance_attributes().get(attrname) for desc in cls.descendants]) or [] 184 185 # A "leaf" class whose instances provide an attribute. 186 187 if attr and not attrs: 188 node._access_type = "instance" 189 node._attr_deduced = attr 190 return 191 192 # A class where instances of subclasses may provide an attribute. 193 194 elif attrs and self_access: 195 if attr: 196 attrs.append(attr) 197 198 node._attrs_deduced = [(a, a.get_value()) for a in attrs] 199 200 # The instances may provide the attribute at the same position. 201 202 positions = set([a.position for a in attrs]) 203 if len(positions) == 1: 204 for position in positions: 205 node._access_type = "positioned" 206 node._position_deduced = position 207 return 208 209 # Otherwise, accessing the attributes is more work. 210 211 node._access_type = "instance" 212 return 213 214 # Find class attributes. 215 # The context will be overridden for compatible class attributes 216 # only. 217 218 attr = cls.all_class_attributes().get(attrname) 219 220 if attr: 221 222 # Constant attributes. 223 224 if attr.is_strict_constant(): 225 if self.provides_constant_result(attr.get_value()): 226 node._access_type = "constant" 227 node._value_deduced = attr.get_value() 228 node._set_context = "set" 229 return 230 231 # Compatible class attributes. 232 233 if attr.defined_within_hierarchy(): 234 node._access_type = "static" 235 node._attr_deduced = attr 236 node._set_context = "set" 237 return 238 239 # Incompatible class attributes. 240 241 elif attr.defined_outside_hierarchy(): 242 node._access_type = "static" 243 node._attr_deduced = attr 244 return 245 246 # Unknown or mixed compatibility. 247 248 node._access_type = "static" 249 node._attr_deduced = attr 250 node._set_context = "cond" 251 return 252 253 # Usage observations, both specific to this node's region of the program 254 # and also applicable to the lifespan of the affected name. 255 256 specific_targets = self.possible_accessors_from_usage(node, defining_users=0) 257 targets = self.possible_accessors_from_usage(node, defining_users=1) 258 259 # Record whether types were already deduced. If not, get types using 260 # only this attribute. 261 262 if not specific_targets or not targets: 263 attribute_targets = self.possible_accessors_for_attribute(attrname) 264 if not specific_targets: 265 specific_targets = attribute_targets 266 if not targets: 267 targets = attribute_targets 268 269 # Get the attributes from the deduced targets. 270 271 node._attrs_deduced_from_specific_usage = self.get_attributes(specific_targets, attrname) 272 node._attrs_deduced_from_usage = attrs = self.get_attributes(targets, attrname) 273 274 # Generate optimisations where only a single attribute applies. 275 276 if attrs and len(attrs) == 1: 277 for attr in attrs: 278 279 # Static attributes, but potentially non-static targets. 280 281 if attr.is_static_attribute(): 282 283 # Static attributes may be accompanied by a different context 284 # depending on the accessor. 285 # NOTE: Should determine whether the context is always replaced. 286 287 node._access_type = "static" 288 node._attr_deduced = attr 289 node._set_context = instance_target and "set" or "cond" 290 return 291 292 # Non-static attributes. 293 294 node._access_type = "instance" 295 node._attr_deduced = attr 296 return 297 298 # Test for compatible attribute positioning. 299 300 elif attrs: 301 positions = set([(attr.is_static_attribute(), attr.position) for attr in attrs]) 302 303 # Permit a position-based access only on non-static attributes since 304 # access to static attributes may happen via instances and thus not 305 # be relative to the accessor but to its parent. 306 307 if len(positions) == 1: 308 for position in positions: 309 if not position[0]: 310 node._access_type = "positioned" 311 node._position_deduced = position[0] 312 return 313 314 # With no usable deductions, generate a table-based access. 315 316 node._access_type = "unknown" 317 node._set_context = "cond" 318 319 visitAssAttr = visitGetattr = _visitAttr 320 321 def visitAssign(self, node): 322 self.expr = self.dispatch(node.expr) 323 for n in node.nodes: 324 self.dispatch(n) 325 326 def visitAssList(self, node): 327 expr = self.expr 328 self.expr = make_instance() 329 for n in node.nodes: 330 self.dispatch(n) 331 self.expr = expr 332 333 visitAssTuple = visitAssList 334 335 def visitAssName(self, node): 336 if self.expr: 337 if isinstance(self.expr, BaseAttr): 338 expr = self.expr.get_value() 339 elif isinstance(self.expr, TypedInstance): 340 expr = self.expr 341 else: 342 return 343 else: 344 return 345 346 attr = node._values and node._values.get(node.name) or None 347 348 # Need to replace any uncertain value with a concrete value. 349 350 if attr: 351 if isinstance(attr, BaseAttr): 352 value = attr.get_value() 353 else: 354 value = attr 355 356 if value and isinstance(value, Instance) and not isinstance(value, TypedInstance): 357 node._values[node.name] = self.expr 358 359 def visitCallFunc(self, node): 360 361 "Identify any concrete types involved with instantiation." 362 363 for n in node.getChildNodes(): 364 self.dispatch(n) 365 366 # Determine whether the target of the invocation refers to a class. 367 368 attr = node.node._attr 369 370 if attr: 371 value = attr.get_value() 372 if value and isinstance(value, Class): 373 return TypedInstance(value) 374 375 def _visitOperator(self, node): 376 377 "Annotate operators with function information." 378 379 self._annotateAttr(node, node._module, node._attr.name) 380 381 visitAdd = \ 382 visitBitand = \ 383 visitBitor = \ 384 visitBitxor = \ 385 visitDiv = \ 386 visitFloorDiv = \ 387 visitInvert = \ 388 visitLeftShift = \ 389 visitMod = \ 390 visitMul = \ 391 visitPower = \ 392 visitRightShift = \ 393 visitSub = \ 394 visitUnaryAdd = \ 395 visitUnarySub = _visitOperator 396 397 # Convenience functions. 398 399 def deduce(program): 400 for module in program.get_importer().get_modules(): 401 DeducedSource(module, program).deduce() 402 403 # vim: tabstop=4 expandtab shiftwidth=4