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 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 const_accesses = self.const_accesses.get(path) 287 288 initialised_ref = None 289 aliased_names = None 290 no_reference = None, None 291 292 # Unwrap invocations. 293 294 if isinstance(name_ref, InvocationRef): 295 invocation = True 296 name_ref = name_ref.name_ref 297 else: 298 invocation = False 299 300 # Obtain a usable reference from names or constants. 301 302 if isinstance(name_ref, ResolvedNameRef): 303 if not name_ref.reference(): 304 return no_reference 305 ref = name_ref.reference() 306 307 # Obtain a reference from instances. 308 309 elif isinstance(name_ref, InstanceRef): 310 if not name_ref.reference(): 311 return no_reference 312 ref = name_ref.reference() 313 314 # Resolve accesses that employ constants. 315 316 elif isinstance(name_ref, AccessRef): 317 ref = None 318 319 if const_accesses: 320 resolved_access = const_accesses.get((name_ref.original_name, name_ref.attrnames)) 321 if resolved_access: 322 objpath, ref, remaining_attrnames = resolved_access 323 if remaining_attrnames: 324 ref = None 325 326 # Accesses that do not employ constants cannot be resolved, 327 # but they may be resolvable later. 328 329 if not ref: 330 331 # Record the path used for tracking purposes 332 # alongside original name, attribute and access 333 # number details. 334 335 aliased_names = [(path, name_ref.original_name, name_ref.attrnames, name_ref.number)] 336 337 return None, aliased_names 338 339 # Attempt to resolve a plain name reference. 340 341 elif isinstance(name_ref, LocalNameRef): 342 key = "%s.%s" % (path, name_ref.name) 343 ref = self.name_references.get(key) 344 345 # Accesses that do not refer to known static objects 346 # cannot be resolved, but they may be resolvable later. 347 348 if not ref: 349 350 # Record the path used for tracking purposes 351 # alongside original name, attribute and access 352 # number details. 353 354 aliased_names = [(path, name_ref.name, None, name_ref.number)] 355 356 return None, aliased_names 357 358 ref = self.get_resolved_object(ref.get_origin()) 359 if not ref: 360 return no_reference 361 362 elif isinstance(name_ref, NameRef): 363 key = "%s.%s" % (path, name_ref.name) 364 ref = self.name_references.get(key) 365 366 ref = ref and self.get_resolved_object(ref.get_origin()) 367 if not ref: 368 return no_reference 369 370 else: 371 return no_reference 372 373 # Resolve any hidden dependencies involving external objects 374 # or unresolved names referring to globals or built-ins. 375 376 if ref.has_kind("<depends>"): 377 ref = self.importer.identify(ref.get_origin()) 378 379 # Convert class invocations to instances. 380 381 if ref and (invocation or ref.has_kind("<invoke>")): 382 target_ref = ref 383 ref = self.convert_invocation(target_ref) 384 385 if not ref or ref.has_kind("<var>"): 386 aliased_names = self.get_aliases_for_target(target_ref.get_origin()) 387 else: 388 initialised_ref = ref 389 390 elif ref and not ref.has_kind("<var>"): 391 initialised_ref = ref 392 393 return initialised_ref, aliased_names 394 395 def get_aliases_for_target(self, path): 396 397 "Return a list of return value locations for the given 'path'." 398 399 return_values = self.importer.all_return_values.get(path) 400 locations = [] 401 402 if return_values: 403 for version in range(0, len(return_values)): 404 locations.append((path, "$return", None, version)) 405 406 return locations 407 408 def resolve_literals(self): 409 410 "Resolve constant value types." 411 412 # Get the constants defined in each namespace. 413 414 for path, constants in self.constants.items(): 415 for constant, n in constants.items(): 416 objpath = "%s.$c%d" % (path, n) 417 _constant, value_type, encoding = self.constant_values[objpath] 418 self.initialised_names[(path, objpath)] = {0 : Reference("<instance>", value_type)} 419 420 # Get the literals defined in each namespace. 421 422 for path, literals in self.literals.items(): 423 for n in range(0, literals): 424 objpath = "%s.$C%d" % (path, n) 425 value_type = self.literal_types[objpath] 426 self.initialised_names[(path, objpath)] = {0 : Reference("<instance>", value_type)} 427 428 # Object resolution. 429 430 def get_resolved_object(self, path, defer=False): 431 432 """ 433 Get the details of an object with the given 'path' within this module. 434 Where the object has not been resolved, None is returned. This differs 435 from the get_object method used elsewhere in that it does not return an 436 unresolved object reference. 437 """ 438 439 if self.objects.has_key(path): 440 ref = self.objects[path] 441 if not defer and ref.has_kind("<depends>"): 442 return None 443 else: 444 return ref 445 else: 446 return None 447 448 # vim: tabstop=4 expandtab shiftwidth=4