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