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 MultipleRef, 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 self._resolve_values(path, name, values) 244 245 def resolve_return_values(self): 246 247 "Resolve return values using name references." 248 249 # Get the return values from each namespace. 250 251 for path, values in self.return_values.items(): 252 253 # Resolve each return value provided by the scope. 254 255 self._resolve_values(path, "$return", values) 256 257 def _resolve_values(self, path, name, values): 258 259 """ 260 Resolve in 'path' the references for 'name' involving the given 261 'values'. 262 """ 263 264 initialised_names = {} 265 aliased_names = {} 266 267 for i, name_ref in enumerate(values): 268 initialised_ref, _aliased_names = self.resolve_reference(path, name_ref) 269 if initialised_ref: 270 initialised_names[i] = initialised_ref 271 if _aliased_names: 272 aliased_names[i] = _aliased_names 273 274 if initialised_names: 275 self.initialised_names[(path, name)] = initialised_names 276 if aliased_names: 277 self.aliased_names[(path, name)] = aliased_names 278 279 def resolve_reference(self, path, name_ref): 280 281 """ 282 Within the namespace 'path', resolve the given 'name_ref', returning any 283 initialised reference, along with any aliased name information. 284 """ 285 286 initialised_ref = None 287 aliased_names = None 288 no_reference = None, None 289 290 # Attempt to obtain a coherent reference from multiple outcomes. 291 292 if isinstance(name_ref, MultipleRef): 293 refs = set() 294 aliases = [] 295 296 for result in name_ref.results: 297 _initialised_ref, _aliased_names = self.resolve_reference(path, result) 298 299 # Unsuitable references at any level cause the result to yield 300 # no reference. 301 302 if not _initialised_ref: 303 refs = None 304 elif refs is not None: 305 refs.add(_initialised_ref) 306 307 if not _aliased_names: 308 aliases = None 309 elif aliases is not None: 310 aliases += _aliased_names 311 312 # Only unambiguous references are returned as initialising 313 # references. 314 315 if refs and len(refs) == 1: 316 return list(refs)[0], aliases 317 else: 318 return None, aliases 319 320 # Unwrap invocations. 321 322 if isinstance(name_ref, InvocationRef): 323 invocation = True 324 name_ref = name_ref.name_ref 325 else: 326 invocation = False 327 328 const_accesses = self.const_accesses.get(path) 329 330 # Obtain a usable reference from names or constants. 331 332 if isinstance(name_ref, ResolvedNameRef): 333 if not name_ref.reference(): 334 return no_reference 335 ref = name_ref.reference() 336 337 # Obtain a reference from instances. 338 339 elif isinstance(name_ref, InstanceRef): 340 if not name_ref.reference(): 341 return no_reference 342 ref = name_ref.reference() 343 344 # Resolve accesses that employ constants. 345 346 elif isinstance(name_ref, AccessRef): 347 ref = None 348 349 if const_accesses: 350 resolved_access = const_accesses.get((name_ref.original_name, name_ref.attrnames)) 351 if resolved_access: 352 objpath, ref, remaining_attrnames = resolved_access 353 if remaining_attrnames: 354 ref = None 355 356 # Accesses that do not employ constants cannot be resolved, 357 # but they may be resolvable later. 358 359 if not ref: 360 361 # Record the path used for tracking purposes 362 # alongside original name, attribute and access 363 # number details. 364 365 aliased_names = [(path, name_ref.original_name, name_ref.attrnames, name_ref.number)] 366 367 return None, aliased_names 368 369 # Attempt to resolve a plain name reference. 370 371 elif isinstance(name_ref, LocalNameRef): 372 key = "%s.%s" % (path, name_ref.name) 373 ref = self.name_references.get(key) 374 375 # Accesses that do not refer to known static objects 376 # cannot be resolved, but they may be resolvable later. 377 378 if not ref: 379 380 # Record the path used for tracking purposes 381 # alongside original name, attribute and access 382 # number details. 383 384 aliased_names = [(path, name_ref.name, None, name_ref.number)] 385 386 return None, aliased_names 387 388 ref = self.get_resolved_object(ref.get_origin()) 389 if not ref: 390 return no_reference 391 392 elif isinstance(name_ref, NameRef): 393 key = "%s.%s" % (path, name_ref.name) 394 ref = self.name_references.get(key) 395 396 ref = ref and self.get_resolved_object(ref.get_origin()) 397 if not ref: 398 return no_reference 399 400 else: 401 return no_reference 402 403 # Resolve any hidden dependencies involving external objects 404 # or unresolved names referring to globals or built-ins. 405 406 if ref.has_kind("<depends>"): 407 ref = self.importer.identify(ref.get_origin()) 408 409 # Convert class invocations to instances. 410 411 if ref and (invocation or ref.has_kind("<invoke>")): 412 target_ref = ref 413 ref = self.convert_invocation(target_ref) 414 415 if not ref or ref.has_kind("<var>"): 416 aliased_names = self.get_aliases_for_target(target_ref.get_origin()) 417 else: 418 initialised_ref = ref 419 420 elif ref and not ref.has_kind("<var>"): 421 initialised_ref = ref 422 423 return initialised_ref, aliased_names 424 425 def get_aliases_for_target(self, path): 426 427 "Return a list of return value locations for the given 'path'." 428 429 return_values = self.importer.all_return_values.get(path) 430 locations = [] 431 432 if return_values: 433 for version in range(0, len(return_values)): 434 locations.append((path, "$return", None, version)) 435 436 return locations 437 438 def resolve_literals(self): 439 440 "Resolve constant value types." 441 442 # Get the constants defined in each namespace. 443 444 for path, constants in self.constants.items(): 445 for constant, n in constants.items(): 446 objpath = "%s.$c%d" % (path, n) 447 _constant, value_type, encoding = self.constant_values[objpath] 448 self.initialised_names[(path, objpath)] = {0 : Reference("<instance>", value_type)} 449 450 # Get the literals defined in each namespace. 451 452 for path, literals in self.literals.items(): 453 for n in range(0, literals): 454 objpath = "%s.$C%d" % (path, n) 455 value_type = self.literal_types[objpath] 456 self.initialised_names[(path, objpath)] = {0 : Reference("<instance>", value_type)} 457 458 # Object resolution. 459 460 def get_resolved_object(self, path, defer=False): 461 462 """ 463 Get the details of an object with the given 'path' within this module. 464 Where the object has not been resolved, None is returned. This differs 465 from the get_object method used elsewhere in that it does not return an 466 unresolved object reference. 467 """ 468 469 if self.objects.has_key(path): 470 ref = self.objects[path] 471 if not defer and ref.has_kind("<depends>"): 472 return None 473 else: 474 return ref 475 else: 476 return None 477 478 # vim: tabstop=4 expandtab shiftwidth=4