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