1 #!/usr/bin/env python 2 3 """ 4 Name resolution. 5 6 Copyright (C) 2016, 2017 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 common import init_item 23 from results import AccessRef, InstanceRef, InvocationRef, LocalNameRef, \ 24 NameRef, ResolvedNameRef 25 from referencing import Reference 26 import sys 27 28 class NameResolving: 29 30 "Resolving names mix-in for inspected modules." 31 32 # Post-inspection resolution activities. 33 34 def resolve(self): 35 36 "Resolve dependencies and complete definitions." 37 38 self.resolve_class_bases() 39 self.check_special() 40 self.check_names_used() 41 self.check_invocations() 42 self.resolve_initialisers() 43 self.resolve_return_values() 44 self.resolve_literals() 45 46 def resolve_class_bases(self): 47 48 "Resolve all class bases since some of them may have been deferred." 49 50 for name, bases in self.classes.items(): 51 resolved = [] 52 bad = [] 53 54 for base in bases: 55 ref = self.importer.identify(base.get_origin()) 56 57 # Obtain the origin of the base class reference. 58 59 if not ref or not ref.has_kind("<class>"): 60 bad.append(base) 61 break 62 63 resolved.append(ref) 64 65 if bad: 66 print >>sys.stderr, "Bases of class %s were not classes: %s" % (name, ", ".join(map(str, bad))) 67 else: 68 self.importer.classes[name] = self.classes[name] = resolved 69 70 def check_special(self): 71 72 "Check special names." 73 74 for name, value in self.special.items(): 75 ref, paths = value 76 self.special[name] = self.importer.identify(ref.get_origin()), paths 77 78 def check_names_used(self): 79 80 "Check the external names used by each scope." 81 82 for key, ref in self.name_references.items(): 83 path, name = key.rsplit(".", 1) 84 self.resolve_accesses(path, name, ref) 85 86 def check_invocations(self): 87 88 "Find invocations amongst module data and replace their results." 89 90 # Find members and replace invocation results with values. This is 91 # effectively the same as is done for initialised names, but refers to 92 # any unchanging value after initialisation. 93 94 for key, ref in self.objects.items(): 95 if ref.has_kind("<invoke>"): 96 ref = self.convert_invocation(ref) 97 self.importer.objects[key] = self.objects[key] = ref 98 99 # Convert name references. 100 101 for key, ref in self.name_references.items(): 102 if ref.has_kind("<invoke>"): 103 ref = self.convert_invocation(ref) 104 self.importer.all_name_references[key] = self.name_references[key] = ref 105 106 # Convert function defaults, which are effectively extra members of the 107 # module, and function locals. 108 109 for fname, parameters in self.function_defaults.items(): 110 l = [] 111 for pname, ref in parameters: 112 if ref.has_kind("<invoke>"): 113 ref = self.convert_invocation(ref) 114 l.append((pname, ref)) 115 self.importer.function_defaults[fname] = self.function_defaults[fname] = l 116 117 # Convert function locals referencing invocations. 118 119 for fname, names in self.function_locals.items(): 120 for name, ref in names.items(): 121 if ref.has_kind("<invoke>"): 122 ref = self.convert_invocation(ref) 123 names[name] = ref 124 125 def convert_invocation(self, ref): 126 127 "Convert the given invocation 'ref', handling instantiation." 128 129 alias = ref.get_name() 130 ref = self.importer.identify(ref.get_origin()) 131 ref = ref and ref.has_kind("<class>") and ref.instance_of() or Reference("<var>") 132 return ref and ref.alias(alias) or None 133 134 def resolve_accesses(self, path, name, ref): 135 136 """ 137 Resolve any unresolved accesses in the function at the given 'path' 138 for the given 'name' corresponding to the indicated 'ref'. Note that 139 this mechanism cannot resolve things like inherited methods because 140 they are not recorded as program objects in their inherited locations. 141 """ 142 143 attr_accesses = self.global_attr_accesses.get(path) 144 all_attrnames = attr_accesses and attr_accesses.get(name) 145 146 if not all_attrnames: 147 return 148 149 # Insist on constant accessors. 150 151 if not ref.has_kind(["<class>", "<module>"]): 152 return 153 154 found_attrnames = set() 155 156 for attrnames in all_attrnames: 157 158 # Start with the resolved name, adding attributes. 159 160 attrs = ref.get_path() 161 remaining = attrnames.split(".") 162 last_ref = ref 163 164 # Add each component, testing for a constant object. 165 166 while remaining: 167 attrname = remaining[0] 168 attrs.append(attrname) 169 del remaining[0] 170 171 # Find any constant object reference. 172 173 attr_ref = self.get_resolved_object(".".join(attrs)) 174 175 # Non-constant accessors terminate the traversal. 176 177 if not attr_ref or not attr_ref.has_kind(["<class>", "<module>", "<function>"]): 178 179 # Provide the furthest constant accessor unless the final 180 # access can be resolved. 181 182 if remaining: 183 remaining.insert(0, attrs.pop()) 184 else: 185 last_ref = attr_ref 186 break 187 188 # Follow any reference to a constant object. 189 # Where the given name refers to an object in another location, 190 # switch to the other location in order to be able to test its 191 # attributes. 192 193 last_ref = attr_ref 194 attrs = attr_ref.get_path() 195 196 # Record a constant accessor only if an object was found 197 # that is different from the namespace involved. 198 199 if last_ref: 200 objpath = ".".join(attrs) 201 if objpath != path: 202 203 if last_ref.has_kind("<invoke>"): 204 last_ref = self.convert_invocation(last_ref) 205 206 # Establish a constant access. 207 208 init_item(self.const_accesses, path, dict) 209 self.const_accesses[path][(name, attrnames)] = (objpath, last_ref, ".".join(remaining)) 210 211 if len(attrs) > 1: 212 found_attrnames.add(attrs[1]) 213 214 # Remove any usage records for the name. 215 216 if found_attrnames: 217 218 # NOTE: Should be only one name version. 219 220 versions = [] 221 for version in self.attr_usage[path][name]: 222 new_usage = set() 223 for usage in version: 224 if found_attrnames.intersection(usage): 225 new_usage.add(tuple(set(usage).difference(found_attrnames))) 226 else: 227 new_usage.add(usage) 228 versions.append(new_usage) 229 230 self.attr_usage[path][name] = versions 231 232 def resolve_initialisers(self): 233 234 "Resolve initialiser values for names." 235 236 # Get the initialisers in each namespace. 237 238 for path, name_initialisers in self.name_initialisers.items(): 239 240 # Resolve values for each name in a scope. 241 242 for name, values in name_initialisers.items(): 243 initialised_names = {} 244 aliased_names = {} 245 246 for i, name_ref in enumerate(values): 247 initialised_ref, _aliased_names = self.resolve_reference(path, name_ref) 248 if initialised_ref: 249 initialised_names[i] = initialised_ref 250 if _aliased_names: 251 aliased_names[i] = _aliased_names 252 253 if initialised_names: 254 self.initialised_names[(path, name)] = initialised_names 255 if aliased_names: 256 self.aliased_names[(path, name)] = aliased_names 257 258 def resolve_return_values(self): 259 260 "Resolve return values using name references." 261 262 # Get the return values from each namespace. 263 264 for path, values in self.return_values.items(): 265 266 # Resolve each return value provided by the scope. 267 268 initialised_names = {} 269 aliased_names = {} 270 271 for i, name_ref in enumerate(values): 272 initialised_ref, _aliased_names = self.resolve_reference(path, name_ref) 273 if initialised_ref: 274 initialised_names[i] = initialised_ref 275 if _aliased_names: 276 aliased_names[i] = _aliased_names 277 278 if initialised_names: 279 self.initialised_names[(path, "$return")] = initialised_names 280 if aliased_names: 281 self.aliased_names[(path, "$return")] = aliased_names 282 283 def resolve_reference(self, path, name_ref): 284 285 """ 286 Within the namespace 'path', resolve the given 'name_ref', returning any 287 initialised reference, along with any aliased name information. 288 """ 289 290 const_accesses = self.const_accesses.get(path) 291 292 initialised_ref = None 293 aliased_names = None 294 no_reference = None, None 295 296 # Unwrap invocations. 297 298 if isinstance(name_ref, InvocationRef): 299 invocation = True 300 name_ref = name_ref.name_ref 301 else: 302 invocation = False 303 304 # Obtain a usable reference from names or constants. 305 306 if isinstance(name_ref, ResolvedNameRef): 307 if not name_ref.reference(): 308 return no_reference 309 ref = name_ref.reference() 310 311 # Obtain a reference from instances. 312 313 elif isinstance(name_ref, InstanceRef): 314 if not name_ref.reference(): 315 return no_reference 316 ref = name_ref.reference() 317 318 # Resolve accesses that employ constants. 319 320 elif isinstance(name_ref, AccessRef): 321 ref = None 322 323 if const_accesses: 324 resolved_access = const_accesses.get((name_ref.original_name, name_ref.attrnames)) 325 if resolved_access: 326 objpath, ref, remaining_attrnames = resolved_access 327 if remaining_attrnames: 328 ref = None 329 330 # Accesses that do not employ constants cannot be resolved, 331 # but they may be resolvable later. 332 333 if not ref: 334 335 # Record the path used for tracking purposes 336 # alongside original name, attribute and access 337 # number details. 338 339 aliased_names = [(path, name_ref.original_name, name_ref.attrnames, name_ref.number)] 340 341 return None, aliased_names 342 343 # Attempt to resolve a plain name reference. 344 345 elif isinstance(name_ref, LocalNameRef): 346 key = "%s.%s" % (path, name_ref.name) 347 ref = self.name_references.get(key) 348 349 # Accesses that do not refer to known static objects 350 # cannot be resolved, but they may be resolvable later. 351 352 if not ref: 353 354 # Record the path used for tracking purposes 355 # alongside original name, attribute and access 356 # number details. 357 358 aliased_names = [(path, name_ref.name, None, name_ref.number)] 359 360 return None, aliased_names 361 362 ref = self.get_resolved_object(ref.get_origin()) 363 if not ref: 364 return no_reference 365 366 elif isinstance(name_ref, NameRef): 367 key = "%s.%s" % (path, name_ref.name) 368 ref = self.name_references.get(key) 369 370 ref = ref and self.get_resolved_object(ref.get_origin()) 371 if not ref: 372 return no_reference 373 374 else: 375 return no_reference 376 377 # Resolve any hidden dependencies involving external objects 378 # or unresolved names referring to globals or built-ins. 379 380 if ref.has_kind("<depends>"): 381 ref = self.importer.identify(ref.get_origin()) 382 383 # Convert class invocations to instances. 384 385 if ref and (invocation or ref.has_kind("<invoke>")): 386 target_ref = ref 387 ref = self.convert_invocation(target_ref) 388 389 if not ref or ref.has_kind("<var>"): 390 aliased_names = self.get_aliases_for_target(target_ref.get_origin()) 391 else: 392 initialised_ref = ref 393 394 elif ref and not ref.has_kind("<var>"): 395 initialised_ref = ref 396 397 return initialised_ref, aliased_names 398 399 def get_aliases_for_target(self, path): 400 401 "Return a list of return value locations for the given 'path'." 402 403 return_values = self.importer.all_return_values.get(path) 404 locations = [] 405 406 if return_values: 407 for version in range(0, len(return_values)): 408 locations.append((path, "$return", None, version)) 409 410 return locations 411 412 def resolve_literals(self): 413 414 "Resolve constant value types." 415 416 # Get the constants defined in each namespace. 417 418 for path, constants in self.constants.items(): 419 for constant, n in constants.items(): 420 objpath = "%s.$c%d" % (path, n) 421 _constant, value_type, encoding = self.constant_values[objpath] 422 self.initialised_names[(path, objpath)] = {0 : Reference("<instance>", value_type)} 423 424 # Get the literals defined in each namespace. 425 426 for path, literals in self.literals.items(): 427 for n in range(0, literals): 428 objpath = "%s.$C%d" % (path, n) 429 value_type = self.literal_types[objpath] 430 self.initialised_names[(path, objpath)] = {0 : Reference("<instance>", value_type)} 431 432 # Object resolution. 433 434 def get_resolved_object(self, path): 435 436 """ 437 Get the details of an object with the given 'path' within this module. 438 Where the object has not been resolved, None is returned. This differs 439 from the get_object method used elsewhere in that it does not return an 440 unresolved object reference. 441 """ 442 443 if self.objects.has_key(path): 444 ref = self.objects[path] 445 if ref.has_kind("<depends>"): 446 return None 447 else: 448 return ref 449 else: 450 return None 451 452 # vim: tabstop=4 expandtab shiftwidth=4