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