Lichen

Annotated importer.py

662:b8733c35d308
2017-03-06 Paul Boddie Incorporated __WITHIN within __HASATTR.
paul@0 1
#!/usr/bin/env python
paul@0 2
paul@0 3
"""
paul@0 4
Import logic.
paul@0 5
paul@0 6
Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013,
paul@510 7
              2014, 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk>
paul@0 8
paul@0 9
This program is free software; you can redistribute it and/or modify it under
paul@0 10
the terms of the GNU General Public License as published by the Free Software
paul@0 11
Foundation; either version 3 of the License, or (at your option) any later
paul@0 12
version.
paul@0 13
paul@0 14
This program is distributed in the hope that it will be useful, but WITHOUT
paul@0 15
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
paul@0 16
FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
paul@0 17
details.
paul@0 18
paul@0 19
You should have received a copy of the GNU General Public License along with
paul@0 20
this program.  If not, see <http://www.gnu.org/licenses/>.
paul@0 21
"""
paul@0 22
paul@0 23
from errors import ProgramError
paul@0 24
from os.path import exists, extsep, getmtime, join
paul@0 25
from os import listdir, makedirs, remove
paul@0 26
from common import init_item, readfile, writefile
paul@13 27
from modules import CachedModule
paul@0 28
from referencing import Reference
paul@0 29
import inspector
paul@0 30
import sys
paul@0 31
paul@0 32
class Importer:
paul@0 33
paul@0 34
    "An import machine, searching for and loading modules."
paul@0 35
paul@526 36
    special_attributes = ("__args__", "__file__", "__fn__", "__name__", "__parent__")
paul@526 37
paul@558 38
    def __init__(self, path, cache=None, verbose=False, warnings=None):
paul@0 39
paul@0 40
        """
paul@0 41
        Initialise the importer with the given search 'path' - a list of
paul@0 42
        directories to search for Python modules.
paul@0 43
paul@0 44
        The optional 'cache' should be the name of a directory used to store
paul@0 45
        cached module information.
paul@0 46
paul@0 47
        The optional 'verbose' parameter causes output concerning the activities
paul@0 48
        of the object to be produced if set to a true value (not the default).
paul@558 49
paul@558 50
        The optional 'warnings' parameter may indicate classes of warnings to be
paul@558 51
        produced.
paul@0 52
        """
paul@0 53
paul@0 54
        self.path = path
paul@0 55
        self.cache = cache
paul@0 56
        self.verbose = verbose
paul@558 57
        self.warnings = warnings
paul@0 58
paul@41 59
        # Module importing queue, required modules, removed modules and active
paul@41 60
        # modules in the final program.
paul@41 61
paul@12 62
        self.to_import = set()
paul@16 63
        self.required = set(["__main__"])
paul@24 64
        self.removed = {}
paul@41 65
        self.modules = {}
paul@12 66
paul@41 67
        # Module relationships and invalidated cached modules.
paul@41 68
paul@12 69
        self.accessing_modules = {}
paul@0 70
        self.invalidated = set()
paul@0 71
paul@425 72
        # Object relationships and dependencies.
paul@425 73
paul@425 74
        self.depends = {}
paul@427 75
        self.module_depends = {}
paul@425 76
paul@41 77
        # Basic program information.
paul@41 78
paul@0 79
        self.objects = {}
paul@0 80
        self.classes = {}
paul@0 81
        self.function_parameters = {}
paul@0 82
        self.function_defaults = {}
paul@109 83
        self.function_locals = {}
paul@0 84
        self.function_targets = {}
paul@0 85
        self.function_arguments = {}
paul@0 86
paul@41 87
        # Unresolved names.
paul@41 88
paul@41 89
        self.missing = set()
paul@41 90
paul@0 91
        # Derived information.
paul@0 92
paul@0 93
        self.subclasses = {}
paul@0 94
paul@0 95
        # Attributes of different object types.
paul@0 96
paul@0 97
        self.all_class_attrs = {}
paul@0 98
        self.all_instance_attrs = {}
paul@0 99
        self.all_instance_attr_constants = {}
paul@0 100
        self.all_combined_attrs = {}
paul@0 101
        self.all_module_attrs = {}
paul@0 102
        self.all_shadowed_attrs = {}
paul@0 103
paul@0 104
        # References to external names and aliases within program units.
paul@0 105
paul@0 106
        self.all_name_references = {}
paul@0 107
        self.all_initialised_names = {}
paul@0 108
        self.all_aliased_names = {}
paul@0 109
paul@0 110
        # General attribute accesses.
paul@0 111
paul@0 112
        self.all_attr_accesses = {}
paul@0 113
        self.all_const_accesses = {}
paul@0 114
        self.all_attr_access_modifiers = {}
paul@0 115
paul@0 116
        # Constant literals and values.
paul@0 117
paul@0 118
        self.all_constants = {}
paul@0 119
        self.all_constant_values = {}
paul@0 120
paul@0 121
        self.make_cache()
paul@0 122
paul@558 123
    def give_warning(self, name):
paul@558 124
paul@558 125
        "Return whether the indicated warning 'name' should be given."
paul@558 126
paul@558 127
        return self.warnings and (name in self.warnings or "all" in self.warnings)
paul@558 128
paul@0 129
    def make_cache(self):
paul@441 130
paul@441 131
        "Make a cache directory if it does not already exist."
paul@441 132
paul@0 133
        if self.cache and not exists(self.cache):
paul@0 134
            makedirs(self.cache)
paul@0 135
paul@0 136
    def check_cache(self, details):
paul@0 137
paul@0 138
        """
paul@0 139
        Check whether the cache applies for the given 'details', invalidating it
paul@0 140
        if it does not.
paul@0 141
        """
paul@0 142
paul@0 143
        recorded_details = self.get_cache_details()
paul@0 144
paul@0 145
        if recorded_details != details:
paul@0 146
            self.remove_cache()
paul@0 147
paul@0 148
        writefile(self.get_cache_details_filename(), details)
paul@0 149
paul@0 150
    def get_cache_details_filename(self):
paul@0 151
paul@0 152
        "Return the filename for the cache details."
paul@0 153
paul@0 154
        return join(self.cache, "$details")
paul@0 155
paul@0 156
    def get_cache_details(self):
paul@0 157
paul@0 158
        "Return details of the cache."
paul@0 159
paul@0 160
        details_filename = self.get_cache_details_filename()
paul@0 161
paul@0 162
        if not exists(details_filename):
paul@0 163
            return None
paul@0 164
        else:
paul@0 165
            return readfile(details_filename)
paul@0 166
paul@0 167
    def remove_cache(self):
paul@0 168
paul@0 169
        "Remove the contents of the cache."
paul@0 170
paul@0 171
        for filename in listdir(self.cache):
paul@0 172
            remove(join(self.cache, filename))
paul@0 173
paul@0 174
    def to_cache(self):
paul@0 175
paul@0 176
        "Write modules to the cache."
paul@0 177
paul@0 178
        if self.cache:
paul@0 179
            for module_name, module in self.modules.items():
paul@0 180
                module.to_cache(join(self.cache, module_name))
paul@0 181
paul@0 182
    # Object retrieval and storage.
paul@0 183
paul@0 184
    def get_object(self, name):
paul@0 185
paul@0 186
        """
paul@0 187
        Return a reference for the given 'name' or None if no such object
paul@0 188
        exists.
paul@0 189
        """
paul@0 190
paul@0 191
        return self.objects.get(name)
paul@0 192
paul@0 193
    def set_object(self, name, value=None):
paul@0 194
paul@0 195
        "Set the object with the given 'name' and the given 'value'."
paul@0 196
paul@0 197
        if isinstance(value, Reference):
paul@0 198
            ref = value.alias(name)
paul@0 199
        else:
paul@0 200
            ref = Reference(value, name)
paul@0 201
paul@0 202
        self.objects[name] = ref
paul@0 203
paul@27 204
    # Identification of both stored object names and name references.
paul@27 205
paul@27 206
    def identify(self, name):
paul@27 207
paul@27 208
        "Identify 'name' using stored object and external name records."
paul@27 209
paul@27 210
        return self.objects.get(name) or self.all_name_references.get(name)
paul@27 211
paul@0 212
    # Indirect object retrieval.
paul@0 213
paul@0 214
    def get_attributes(self, ref, attrname):
paul@0 215
paul@0 216
        """
paul@0 217
        Return attributes provided by 'ref' for 'attrname'. Class attributes
paul@0 218
        may be provided by instances.
paul@0 219
        """
paul@0 220
paul@0 221
        kind = ref.get_kind()
paul@0 222
        if kind == "<class>":
paul@0 223
            ref = self.get_class_attribute(ref.get_origin(), attrname)
paul@0 224
            return ref and set([ref]) or set()
paul@0 225
        elif kind == "<instance>":
paul@0 226
            return self.get_combined_attributes(ref.get_origin(), attrname)
paul@0 227
        elif kind == "<module>":
paul@0 228
            ref = self.get_module_attribute(ref.get_origin(), attrname)
paul@0 229
            return ref and set([ref]) or set()
paul@0 230
        else:
paul@0 231
            return set()
paul@0 232
paul@0 233
    def get_class_attribute(self, object_type, attrname):
paul@0 234
paul@0 235
        "Return from 'object_type' the details of class attribute 'attrname'."
paul@0 236
paul@324 237
        attrs = self.all_class_attrs.get(object_type)
paul@324 238
        attr = attrs and attrs.get(attrname)
paul@0 239
        return attr and self.get_object(attr)
paul@0 240
paul@0 241
    def get_instance_attributes(self, object_type, attrname):
paul@0 242
paul@0 243
        """
paul@0 244
        Return from 'object_type' the details of instance attribute 'attrname'.
paul@0 245
        """
paul@0 246
paul@0 247
        consts = self.all_instance_attr_constants.get(object_type)
paul@0 248
        attrs = set()
paul@0 249
        for attr in self.all_instance_attrs[object_type].get(attrname, []):
paul@0 250
            attrs.add(consts and consts.get(attrname) or Reference("<var>", attr))
paul@0 251
        return attrs
paul@0 252
paul@0 253
    def get_combined_attributes(self, object_type, attrname):
paul@0 254
paul@0 255
        """
paul@0 256
        Return from 'object_type' the details of class or instance attribute
paul@0 257
        'attrname'.
paul@0 258
        """
paul@0 259
paul@0 260
        ref = self.get_class_attribute(object_type, attrname)
paul@0 261
        refs = ref and set([ref]) or set()
paul@0 262
        refs.update(self.get_instance_attributes(object_type, attrname))
paul@0 263
        return refs
paul@0 264
paul@0 265
    def get_module_attribute(self, object_type, attrname):
paul@0 266
paul@0 267
        "Return from 'object_type' the details of module attribute 'attrname'."
paul@0 268
paul@0 269
        if attrname in self.all_module_attrs[object_type]:
paul@0 270
            return self.get_object("%s.%s" % (object_type, attrname))
paul@0 271
        else:
paul@0 272
            return None
paul@0 273
paul@96 274
    # Convenience methods for deducing which kind of object provided an
paul@96 275
    # attribute.
paul@96 276
paul@96 277
    def get_attribute_provider(self, ref, attrname):
paul@96 278
paul@96 279
        """
paul@96 280
        Return the kind of provider of the attribute accessed via 'ref' using
paul@96 281
        'attrname'.
paul@96 282
        """
paul@96 283
paul@96 284
        kind = ref.get_kind()
paul@96 285
paul@96 286
        if kind in ["<class>", "<module>"]:
paul@96 287
            return kind
paul@96 288
        else:
paul@96 289
            return self.get_instance_attribute_provider(ref.get_origin(), attrname)
paul@96 290
paul@96 291
    def get_instance_attribute_provider(self, object_type, attrname):
paul@96 292
paul@96 293
        """
paul@96 294
        Return the kind of provider of the attribute accessed via an instance of
paul@96 295
        'object_type' using 'attrname'.
paul@96 296
        """
paul@96 297
paul@96 298
        if self.get_class_attribute(object_type, attrname):
paul@96 299
            return "<class>"
paul@96 300
        else:
paul@96 301
            return "<instance>"
paul@96 302
paul@0 303
    # Module management.
paul@0 304
paul@16 305
    def queue_module(self, name, accessor, required=False):
paul@12 306
paul@12 307
        """
paul@12 308
        Queue the module with the given 'name' for import from the given
paul@16 309
        'accessor' module. If 'required' is true (it is false by default), the
paul@16 310
        module will be required in the final program.
paul@12 311
        """
paul@12 312
paul@12 313
        if not self.modules.has_key(name):
paul@12 314
            self.to_import.add(name)
paul@12 315
paul@16 316
        if required:
paul@16 317
            self.required.add(name)
paul@16 318
paul@12 319
        init_item(self.accessing_modules, name, set)
paul@16 320
        self.accessing_modules[name].add(accessor.name)
paul@12 321
paul@0 322
    def get_modules(self):
paul@0 323
paul@0 324
        "Return all modules known to the importer."
paul@0 325
paul@0 326
        return self.modules.values()
paul@0 327
paul@12 328
    def get_module(self, name):
paul@0 329
paul@0 330
        "Return the module with the given 'name'."
paul@0 331
paul@0 332
        if not self.modules.has_key(name):
paul@0 333
            return None
paul@0 334
paul@12 335
        return self.modules[name]
paul@0 336
paul@0 337
    # Program operations.
paul@0 338
paul@0 339
    def initialise(self, filename, reset=False):
paul@0 340
paul@0 341
        """
paul@0 342
        Initialise a program whose main module is 'filename', resetting the
paul@0 343
        cache if 'reset' is true. Return the main module.
paul@0 344
        """
paul@0 345
paul@0 346
        if reset:
paul@0 347
            self.remove_cache()
paul@0 348
        self.check_cache(filename)
paul@0 349
paul@0 350
        # Load the program itself.
paul@0 351
paul@0 352
        m = self.load_from_file(filename)
paul@0 353
paul@12 354
        # Load any queued modules.
paul@12 355
paul@12 356
        while self.to_import:
paul@12 357
            for name in list(self.to_import): # avoid mutation issue
paul@12 358
                self.load(name)
paul@12 359
paul@12 360
        # Resolve dependencies between modules.
paul@12 361
paul@12 362
        self.resolve()
paul@12 363
paul@16 364
        # Record the type of all classes.
paul@16 365
paul@16 366
        self.type_ref = self.get_object("__builtins__.type")
paul@16 367
paul@0 368
        # Resolve dependencies within the program.
paul@0 369
paul@12 370
        for module in self.modules.values():
paul@12 371
            module.complete()
paul@0 372
paul@16 373
        # Remove unneeded modules.
paul@16 374
paul@16 375
        all_modules = self.modules.items()
paul@16 376
paul@16 377
        for name, module in all_modules:
paul@16 378
            if name not in self.required:
paul@16 379
                module.unpropagate()
paul@16 380
                del self.modules[name]
paul@24 381
                self.removed[name] = module
paul@16 382
paul@68 383
        # Collect redundant objects.
paul@68 384
paul@68 385
        for module in self.removed.values():
paul@68 386
            module.collect()
paul@68 387
paul@68 388
        # Assert module objects where aliases have been removed.
paul@68 389
paul@68 390
        for name in self.required:
paul@68 391
            if not self.objects.has_key(name):
paul@68 392
                self.objects[name] = Reference("<module>", name)
paul@68 393
paul@0 394
        return m
paul@0 395
paul@0 396
    def finalise(self):
paul@0 397
paul@41 398
        """
paul@41 399
        Finalise the inspected program, returning whether the program could be
paul@41 400
        finalised.
paul@41 401
        """
paul@41 402
paul@358 403
        self.finalise_classes()
paul@423 404
        self.add_init_dependencies()
paul@358 405
        self.to_cache()
paul@358 406
paul@41 407
        if self.missing:
paul@41 408
            return False
paul@0 409
paul@0 410
        self.set_class_types()
paul@0 411
        self.define_instantiators()
paul@0 412
        self.collect_constants()
paul@0 413
paul@41 414
        return True
paul@41 415
paul@12 416
    # Supporting operations.
paul@12 417
paul@12 418
    def resolve(self):
paul@12 419
paul@12 420
        "Resolve dependencies between modules."
paul@12 421
paul@35 422
        self.waiting = {}
paul@35 423
paul@35 424
        for module in self.modules.values():
paul@35 425
paul@35 426
            # Resolve all deferred references in each module.
paul@12 427
paul@391 428
            original_deferred = []
paul@391 429
paul@35 430
            for ref in module.deferred:
paul@391 431
paul@391 432
                # Retain original references for caching.
paul@391 433
paul@391 434
                original_deferred.append(ref.copy())
paul@391 435
paul@391 436
                # Update references throughout the program.
paul@391 437
paul@35 438
                found = self.find_dependency(ref)
paul@35 439
                if not found:
paul@41 440
                    self.missing.add((module.name, ref.get_origin()))
paul@35 441
paul@35 442
                # Record the resolved names and identify required modules.
paul@12 443
paul@35 444
                else:
paul@170 445
                    # Find the providing module of this reference.
paul@170 446
                    # Where definitive details of the origin cannot be found,
paul@170 447
                    # identify the provider using the deferred reference.
paul@170 448
                    # NOTE: This may need to test for static origins.
paul@170 449
paul@170 450
                    provider = self.get_module_provider(found.unresolved() and ref or found)
paul@35 451
                    ref.mutate(found)
paul@35 452
paul@186 453
                    # Record any external dependency.
paul@186 454
paul@186 455
                    if provider and provider != module.name:
paul@186 456
paul@543 457
                        # Handle built-in modules accidentally referenced by
paul@543 458
                        # names.
paul@543 459
paul@543 460
                        if provider == "__builtins__" and found.has_kind("<module>"):
paul@543 461
                            raise ProgramError("Name %s, used by %s, refers to module %s." %
paul@543 462
                                               (found.leaf(), module.name, found.get_origin()))
paul@543 463
paul@186 464
                        # Record the provider dependency.
paul@16 465
paul@35 466
                        module.required.add(provider)
paul@35 467
                        self.accessing_modules[provider].add(module.name)
paul@35 468
paul@35 469
                        # Postpone any inclusion of the provider until this
paul@35 470
                        # module becomes required.
paul@12 471
paul@35 472
                        if module.name not in self.required:
paul@35 473
                            init_item(self.waiting, module.name, set)
paul@35 474
                            self.waiting[module.name].add(provider)
paul@418 475
                            if self.verbose:
paul@418 476
                                print >>sys.stderr, "Noting", provider, "for", ref, "from", module.name
paul@35 477
paul@35 478
                        # Make this module required in the accessing module.
paul@32 479
paul@53 480
                        elif provider not in self.required:
paul@35 481
                            self.required.add(provider)
paul@53 482
                            if self.verbose:
paul@418 483
                                print >>sys.stderr, "Requiring", provider, "for", ref, "from", module.name
paul@35 484
paul@425 485
                        # Record a module ordering dependency.
paul@425 486
paul@429 487
                        if not found.static() or self.is_dynamic_class(found) or self.is_dynamic_callable(found):
paul@427 488
                            self.add_module_dependency(module.name, provider)
paul@425 489
paul@425 490
            # Restore the original references so that they may be read back in
paul@425 491
            # and produce the same results.
paul@425 492
paul@391 493
            module.deferred = original_deferred
paul@391 494
paul@38 495
        # Check modules again to see if they are now required and should now
paul@38 496
        # cause the inclusion of other modules providing objects to the program.
paul@38 497
paul@35 498
        for module_name in self.waiting.keys():
paul@35 499
            self.require_providers(module_name)
paul@16 500
paul@423 501
        self.add_special_dependencies()
paul@427 502
        self.add_module_dependencies()
paul@419 503
paul@35 504
    def require_providers(self, module_name):
paul@38 505
paul@38 506
        """
paul@38 507
        Test if 'module_name' is itself required and, if so, require modules
paul@38 508
        containing objects provided to the module.
paul@38 509
        """
paul@38 510
paul@35 511
        if module_name in self.required and self.waiting.has_key(module_name):
paul@35 512
            for provider in self.waiting[module_name]:
paul@35 513
                if provider not in self.required:
paul@35 514
                    self.required.add(provider)
paul@53 515
                    if self.verbose:
paul@53 516
                        print >>sys.stderr, "Requiring", provider
paul@35 517
                    self.require_providers(provider)
paul@32 518
paul@423 519
    def add_special_dependencies(self):
paul@423 520
paul@423 521
        "Add dependencies due to the use of special names in namespaces."
paul@423 522
paul@423 523
        for module in self.modules.values():
paul@423 524
            for ref, paths in module.special.values():
paul@423 525
                for path in paths:
paul@423 526
                    self.add_dependency(path, ref.get_origin())
paul@423 527
paul@423 528
    def add_init_dependencies(self):
paul@423 529
paul@423 530
        "Add dependencies related to object initialisation."
paul@418 531
paul@423 532
        for name in self.classes.keys():
paul@423 533
            if self.is_dynamic_class(name):
paul@423 534
paul@423 535
                # Make subclasses depend on any class with non-static
paul@423 536
                # attributes, plus its module for the initialisation.
paul@418 537
paul@423 538
                for subclass in self.subclasses[name]:
paul@423 539
                    ref = Reference("<class>", subclass)
paul@423 540
                    self.add_dependency(subclass, name)
paul@423 541
                    self.add_dependency(subclass, self.get_module_provider(ref))
paul@423 542
paul@423 543
                # Also make the class dependent on its module for
paul@423 544
                # initialisation.
paul@423 545
paul@423 546
                ref = Reference("<class>", name)
paul@423 547
                self.add_dependency(name, self.get_module_provider(ref))
paul@418 548
paul@423 549
        for name in self.function_defaults.keys():
paul@423 550
            if self.is_dynamic_callable(name):
paul@423 551
paul@423 552
                # Make functions with defaults requiring initialisation depend
paul@428 553
                # on the parent scope, if a function, or the module scope.
paul@423 554
paul@423 555
                ref = Reference("<function>", name)
paul@428 556
                parent_ref = self.get_object(ref.parent())
paul@428 557
paul@428 558
                # Function no longer present in the program.
paul@428 559
paul@428 560
                if not parent_ref:
paul@428 561
                    continue
paul@428 562
paul@428 563
                if parent_ref.has_kind("<class>"):
paul@428 564
                    parent = self.get_module_provider(parent_ref)
paul@428 565
                else:
paul@428 566
                    parent = parent_ref.get_origin()
paul@428 567
paul@428 568
                self.add_dependency(name, parent)
paul@423 569
paul@427 570
    def add_module_dependencies(self):
paul@427 571
paul@427 572
        "Record module-based dependencies."
paul@427 573
paul@427 574
        for module_name, providers in self.module_depends.items():
paul@427 575
            if self.modules.has_key(module_name):
paul@427 576
                for provider in providers:
paul@427 577
                    if self.modules.has_key(provider):
paul@427 578
                        self.add_dependency(module_name, provider)
paul@427 579
paul@423 580
    def add_dependency(self, path, origin):
paul@423 581
paul@423 582
        "Add dependency details for 'path' involving 'origin'."
paul@423 583
paul@427 584
        if origin and not origin.startswith("%s." % path):
paul@423 585
            init_item(self.depends, path, set)
paul@423 586
            self.depends[path].add(origin)
paul@423 587
paul@427 588
    def add_module_dependency(self, module_name, provider):
paul@427 589
paul@427 590
        "Add dependency details for 'module_name' involving 'provider'."
paul@427 591
paul@427 592
        if provider:
paul@427 593
            init_item(self.module_depends, module_name, set)
paul@427 594
            self.module_depends[module_name].add(provider)
paul@427 595
paul@427 596
    def condense_dependencies(self):
paul@427 597
paul@427 598
        """
paul@427 599
        Condense the dependencies by removing all functions that do not need
paul@427 600
        initialisation.
paul@427 601
        """
paul@427 602
paul@427 603
        d = {}
paul@427 604
        for path, depends in self.depends.items():
paul@427 605
            d[path] = {}
paul@427 606
            d[path] = self.condense_dependency_entry(depends, d)
paul@427 607
paul@427 608
        self.depends = {}
paul@427 609
paul@427 610
        for path, depends in d.items():
paul@427 611
            if depends:
paul@427 612
                self.depends[path] = depends
paul@427 613
paul@427 614
    def condense_dependency_entry(self, depends, d):
paul@427 615
        l = set()
paul@427 616
        for depend in depends:
paul@427 617
            if self.modules.has_key(depend) or self.classes.has_key(depend) or \
paul@427 618
               self.is_dynamic_callable(depend):
paul@427 619
paul@427 620
                l.add(depend)
paul@427 621
            else:
paul@427 622
                deps = d.get(depend)
paul@427 623
                if deps:
paul@427 624
                    l.update(self.condense_dependency_entry(deps, d))
paul@427 625
        return l
paul@427 626
paul@428 627
    def is_dynamic(self, ref):
paul@428 628
        return not ref or not ref.static() and not ref.is_constant_alias() and not ref.is_predefined_value()
paul@428 629
paul@423 630
    def is_dynamic_class(self, name):
paul@423 631
paul@423 632
        """
paul@423 633
        Return whether 'name' refers to a class with members that must be
paul@423 634
        initialised dynamically.
paul@423 635
        """
paul@423 636
paul@423 637
        attrs = self.all_class_attrs.get(name)
paul@423 638
paul@423 639
        if not attrs:
paul@418 640
            return False
paul@418 641
paul@423 642
        for attrname, attr in attrs.items():
paul@423 643
            if attrname in self.special_attributes:
paul@423 644
                continue
paul@428 645
            ref = attr and self.get_object(attr)
paul@428 646
            if self.is_dynamic(ref):
paul@423 647
                return True
paul@423 648
paul@423 649
        return False
paul@423 650
paul@423 651
    def is_dynamic_callable(self, name):
paul@334 652
paul@334 653
        """
paul@423 654
        Return whether 'name' refers to a callable employing defaults that may
paul@334 655
        need initialising before the callable can be used.
paul@334 656
        """
paul@334 657
paul@338 658
        # Find any defaults for the function or method.
paul@338 659
paul@423 660
        defaults = self.function_defaults.get(name)
paul@338 661
        if not defaults:
paul@338 662
            return False
paul@338 663
paul@338 664
        # Identify non-constant defaults.
paul@338 665
paul@338 666
        for name, ref in defaults:
paul@428 667
            if self.is_dynamic(ref):
paul@338 668
                return True
paul@338 669
paul@338 670
        return False
paul@334 671
paul@423 672
    def order_objects(self):
paul@186 673
paul@423 674
        "Produce an object initialisation ordering."
paul@186 675
paul@427 676
        self.condense_dependencies()
paul@427 677
paul@313 678
        # Record the number of modules using or depending on each module.
paul@313 679
paul@313 680
        usage = {}
paul@186 681
paul@427 682
        # Record path-based dependencies.
paul@427 683
paul@423 684
        for path in self.depends.keys():
paul@427 685
            usage[path] = set()
paul@313 686
paul@423 687
        for path, depends in self.depends.items():
paul@423 688
            for origin in depends:
paul@427 689
                init_item(usage, origin, set)
paul@427 690
                usage[origin].add(path)
paul@313 691
paul@313 692
        # Produce an ordering by obtaining exposed modules (required by modules
paul@313 693
        # already processed) and putting them at the start of the list.
paul@186 694
paul@313 695
        ordered = []
paul@313 696
paul@313 697
        while usage:
paul@423 698
            have_next = False
paul@423 699
paul@423 700
            for path, n in usage.items():
paul@427 701
                if not n:
paul@423 702
                    ordered.insert(0, path)
paul@423 703
                    depends = self.depends.get(path)
paul@423 704
paul@423 705
                    # Reduce usage of the referenced objects.
paul@186 706
paul@423 707
                    if depends:
paul@423 708
                        for origin in depends:
paul@427 709
                            usage[origin].remove(path)
paul@186 710
paul@423 711
                    del usage[path]
paul@423 712
                    have_next = True
paul@186 713
paul@423 714
            if not have_next:
paul@423 715
                raise ProgramError("Modules with unresolvable dependencies exist: %s" % ", ".join(usage.keys()))
paul@313 716
paul@463 717
        if "__main__" in ordered:
paul@463 718
            ordered.remove("__main__")
paul@463 719
paul@313 720
        ordered.append("__main__")
paul@186 721
        return ordered
paul@186 722
paul@423 723
    def order_modules(self):
paul@418 724
paul@423 725
        "Produce a module initialisation ordering."
paul@418 726
paul@423 727
        ordered = self.order_objects()
paul@423 728
        filtered = []
paul@418 729
paul@423 730
        for module_name in self.modules.keys():
paul@423 731
            if module_name not in ordered:
paul@423 732
                filtered.append(module_name)
paul@418 733
paul@423 734
        for path in ordered:
paul@423 735
            if self.modules.has_key(path):
paul@423 736
                filtered.append(path)
paul@418 737
paul@423 738
        return filtered
paul@186 739
paul@12 740
    def find_dependency(self, ref):
paul@12 741
paul@12 742
        "Find the ultimate dependency for 'ref'."
paul@12 743
paul@12 744
        found = set()
paul@12 745
        while ref and ref.has_kind("<depends>") and not ref in found:
paul@12 746
            found.add(ref)
paul@35 747
            ref = self.identify(ref.get_origin())
paul@12 748
        return ref
paul@12 749
paul@16 750
    def get_module_provider(self, ref):
paul@16 751
paul@16 752
        "Identify the provider of the given 'ref'."
paul@16 753
paul@16 754
        for ancestor in ref.ancestors():
paul@16 755
            if self.modules.has_key(ancestor):
paul@16 756
                return ancestor
paul@16 757
        return None
paul@16 758
paul@0 759
    def finalise_classes(self):
paul@0 760
paul@0 761
        "Finalise the class relationships and attributes."
paul@0 762
paul@0 763
        self.derive_inherited_attrs()
paul@0 764
        self.derive_subclasses()
paul@0 765
        self.derive_shadowed_attrs()
paul@0 766
paul@0 767
    def derive_inherited_attrs(self):
paul@0 768
paul@0 769
        "Derive inherited attributes for classes throughout the program."
paul@0 770
paul@0 771
        for name in self.classes.keys():
paul@0 772
            self.propagate_attrs_for_class(name)
paul@0 773
paul@0 774
    def propagate_attrs_for_class(self, name, visited=None):
paul@0 775
paul@0 776
        "Propagate inherited attributes for class 'name'."
paul@0 777
paul@0 778
        # Visit classes only once.
paul@0 779
paul@0 780
        if self.all_combined_attrs.has_key(name):
paul@0 781
            return
paul@0 782
paul@0 783
        visited = visited or []
paul@0 784
paul@0 785
        if name in visited:
paul@0 786
            raise ProgramError, "Class %s may not inherit from itself: %s -> %s." % (name, " -> ".join(visited), name)
paul@0 787
paul@0 788
        visited.append(name)
paul@0 789
paul@0 790
        class_attrs = {}
paul@0 791
        instance_attrs = {}
paul@0 792
paul@0 793
        # Aggregate the attributes from base classes, recording the origins of
paul@0 794
        # applicable attributes.
paul@0 795
paul@0 796
        for base in self.classes[name][::-1]:
paul@0 797
paul@0 798
            # Get the identity of the class from the reference.
paul@0 799
paul@0 800
            base = base.get_origin()
paul@0 801
paul@0 802
            # Define the base class completely before continuing with this
paul@0 803
            # class.
paul@0 804
paul@0 805
            self.propagate_attrs_for_class(base, visited)
paul@0 806
            class_attrs.update(self.all_class_attrs[base])
paul@0 807
paul@0 808
            # Instance attribute origins are combined if different.
paul@0 809
paul@0 810
            for key, values in self.all_instance_attrs[base].items():
paul@0 811
                init_item(instance_attrs, key, set)
paul@0 812
                instance_attrs[key].update(values)
paul@0 813
paul@0 814
        # Class attributes override those defined earlier in the hierarchy.
paul@0 815
paul@0 816
        class_attrs.update(self.all_class_attrs.get(name, {}))
paul@0 817
paul@0 818
        # Instance attributes are merely added if not already defined.
paul@0 819
paul@0 820
        for key in self.all_instance_attrs.get(name, []):
paul@0 821
            if not instance_attrs.has_key(key):
paul@0 822
                instance_attrs[key] = set(["%s.%s" % (name, key)])
paul@0 823
paul@0 824
        self.all_class_attrs[name] = class_attrs
paul@0 825
        self.all_instance_attrs[name] = instance_attrs
paul@0 826
        self.all_combined_attrs[name] = set(class_attrs.keys()).union(instance_attrs.keys())
paul@0 827
paul@0 828
    def derive_subclasses(self):
paul@0 829
paul@0 830
        "Derive subclass details for classes."
paul@0 831
paul@0 832
        for name, bases in self.classes.items():
paul@0 833
            for base in bases:
paul@0 834
paul@0 835
                # Get the identity of the class from the reference.
paul@0 836
paul@0 837
                base = base.get_origin()
paul@0 838
                self.subclasses[base].add(name)
paul@0 839
paul@0 840
    def derive_shadowed_attrs(self):
paul@0 841
paul@0 842
        "Derive shadowed attributes for classes."
paul@0 843
paul@0 844
        for name, attrs in self.all_instance_attrs.items():
paul@0 845
            attrs = set(attrs.keys()).intersection(self.all_class_attrs[name].keys())
paul@0 846
            if attrs:
paul@0 847
                self.all_shadowed_attrs[name] = attrs
paul@0 848
paul@0 849
    def set_class_types(self):
paul@0 850
paul@0 851
        "Set the type of each class."
paul@0 852
paul@0 853
        for attrs in self.all_class_attrs.values():
paul@16 854
            attrs["__class__"] = self.type_ref.get_origin()
paul@0 855
paul@0 856
    def define_instantiators(self):
paul@0 857
paul@0 858
        """
paul@0 859
        Consolidate parameter and default details, incorporating initialiser
paul@0 860
        details to define instantiator signatures.
paul@0 861
        """
paul@0 862
paul@0 863
        for cls, attrs in self.all_class_attrs.items():
paul@0 864
            initialiser = attrs["__init__"]
paul@119 865
            self.function_parameters[cls] = self.function_parameters[initialiser]
paul@0 866
            self.function_defaults[cls] = self.function_defaults[initialiser]
paul@0 867
paul@0 868
    def collect_constants(self):
paul@0 869
paul@0 870
        "Get constants from all active modules."
paul@0 871
paul@0 872
        for module in self.modules.values():
paul@0 873
            self.all_constants.update(module.constants)
paul@0 874
paul@0 875
    # Import methods.
paul@0 876
paul@0 877
    def find_in_path(self, name):
paul@0 878
paul@0 879
        """
paul@0 880
        Find the given module 'name' in the search path, returning None where no
paul@0 881
        such module could be found, or a 2-tuple from the 'find' method
paul@0 882
        otherwise.
paul@0 883
        """
paul@0 884
paul@0 885
        for d in self.path:
paul@0 886
            m = self.find(d, name)
paul@0 887
            if m: return m
paul@0 888
        return None
paul@0 889
paul@0 890
    def find(self, d, name):
paul@0 891
paul@0 892
        """
paul@0 893
        In the directory 'd', find the given module 'name', where 'name' can
paul@0 894
        either refer to a single file module or to a package. Return None if the
paul@0 895
        'name' cannot be associated with either a file or a package directory,
paul@0 896
        or a 2-tuple from '_find_package' or '_find_module' otherwise.
paul@0 897
        """
paul@0 898
paul@0 899
        m = self._find_package(d, name)
paul@0 900
        if m: return m
paul@0 901
        m = self._find_module(d, name)
paul@0 902
        if m: return m
paul@0 903
        return None
paul@0 904
paul@0 905
    def _find_module(self, d, name):
paul@0 906
paul@0 907
        """
paul@0 908
        In the directory 'd', find the given module 'name', returning None where
paul@0 909
        no suitable file exists in the directory, or a 2-tuple consisting of
paul@0 910
        None (indicating that no package directory is involved) and a filename
paul@0 911
        indicating the location of the module.
paul@0 912
        """
paul@0 913
paul@0 914
        name_py = name + extsep + "py"
paul@0 915
        filename = self._find_file(d, name_py)
paul@0 916
        if filename:
paul@0 917
            return None, filename
paul@0 918
        return None
paul@0 919
paul@0 920
    def _find_package(self, d, name):
paul@0 921
paul@0 922
        """
paul@0 923
        In the directory 'd', find the given package 'name', returning None
paul@0 924
        where no suitable package directory exists, or a 2-tuple consisting of
paul@0 925
        a directory (indicating the location of the package directory itself)
paul@0 926
        and a filename indicating the location of the __init__.py module which
paul@0 927
        declares the package's top-level contents.
paul@0 928
        """
paul@0 929
paul@0 930
        filename = self._find_file(d, name)
paul@0 931
        if filename:
paul@0 932
            init_py = "__init__" + extsep + "py"
paul@0 933
            init_py_filename = self._find_file(filename, init_py)
paul@0 934
            if init_py_filename:
paul@0 935
                return filename, init_py_filename
paul@0 936
        return None
paul@0 937
paul@0 938
    def _find_file(self, d, filename):
paul@0 939
paul@0 940
        """
paul@0 941
        Return the filename obtained when searching the directory 'd' for the
paul@0 942
        given 'filename', or None if no actual file exists for the filename.
paul@0 943
        """
paul@0 944
paul@0 945
        filename = join(d, filename)
paul@0 946
        if exists(filename):
paul@0 947
            return filename
paul@0 948
        else:
paul@0 949
            return None
paul@0 950
paul@12 951
    def load(self, name):
paul@0 952
paul@0 953
        """
paul@0 954
        Load the module or package with the given 'name'. Return an object
paul@0 955
        referencing the loaded module or package, or None if no such module or
paul@0 956
        package exists.
paul@0 957
        """
paul@0 958
paul@0 959
        # Loaded modules are returned immediately.
paul@0 960
        # Modules may be known but not yet loading (having been registered as
paul@0 961
        # submodules), loading, loaded, or completely unknown.
paul@0 962
paul@12 963
        module = self.get_module(name)
paul@0 964
paul@0 965
        if module:
paul@12 966
            return self.modules[name]
paul@0 967
paul@0 968
        # Otherwise, modules are loaded.
paul@0 969
paul@0 970
        # Split the name into path components, and try to find the uppermost in
paul@0 971
        # the search path.
paul@0 972
paul@0 973
        path = name.split(".")
paul@0 974
        path_so_far = []
paul@12 975
        module = None
paul@0 976
paul@0 977
        for p in path:
paul@0 978
paul@0 979
            # Get the module's filesystem details.
paul@0 980
paul@0 981
            if not path_so_far:
paul@0 982
                m = self.find_in_path(p)
paul@0 983
            elif d:
paul@0 984
                m = self.find(d, p)
paul@0 985
            else:
paul@0 986
                m = None
paul@0 987
paul@0 988
            path_so_far.append(p)
paul@0 989
            module_name = ".".join(path_so_far)
paul@0 990
paul@469 991
            # Raise an exception if the module could not be located.
paul@329 992
paul@0 993
            if not m:
paul@469 994
                raise ProgramError("Module not found: %s" % name)
paul@0 995
paul@329 996
            # Get the directory and module filename.
paul@0 997
paul@0 998
            d, filename = m
paul@0 999
paul@329 1000
        # Get the module itself.
paul@329 1001
paul@329 1002
        return self.load_from_file(filename, module_name)
paul@0 1003
paul@12 1004
    def load_from_file(self, filename, module_name=None):
paul@0 1005
paul@0 1006
        "Load the module from the given 'filename'."
paul@0 1007
paul@0 1008
        if module_name is None:
paul@0 1009
            module_name = "__main__"
paul@0 1010
paul@0 1011
        module = self.modules.get(module_name)
paul@0 1012
paul@0 1013
        if not module:
paul@0 1014
paul@0 1015
            # Try to load from cache.
paul@0 1016
paul@12 1017
            module = self.load_from_cache(filename, module_name)
paul@0 1018
            if module:
paul@0 1019
                return module
paul@0 1020
paul@0 1021
            # If no cache entry exists, load from file.
paul@0 1022
paul@0 1023
            module = inspector.InspectedModule(module_name, self)
paul@0 1024
            self.add_module(module_name, module)
paul@0 1025
            self.update_cache_validity(module)
paul@0 1026
paul@12 1027
            self._load(module, module_name, lambda m: m.parse, filename)
paul@0 1028
paul@0 1029
        return module
paul@0 1030
paul@0 1031
    def update_cache_validity(self, module):
paul@0 1032
paul@0 1033
        "Make 'module' valid in the cache, but invalidate accessing modules."
paul@0 1034
paul@12 1035
        accessing = self.accessing_modules.get(module.name)
paul@12 1036
        if accessing:
paul@12 1037
            self.invalidated.update(accessing)
paul@0 1038
        if module.name in self.invalidated:
paul@0 1039
            self.invalidated.remove(module.name)
paul@0 1040
paul@0 1041
    def source_is_new(self, filename, module_name):
paul@0 1042
paul@0 1043
        "Return whether 'filename' is newer than the cached 'module_name'."
paul@0 1044
paul@0 1045
        if self.cache:
paul@0 1046
            cache_filename = join(self.cache, module_name)
paul@0 1047
            return not exists(cache_filename) or \
paul@0 1048
                getmtime(filename) > getmtime(cache_filename) or \
paul@0 1049
                module_name in self.invalidated
paul@0 1050
        else:
paul@0 1051
            return True
paul@0 1052
paul@12 1053
    def load_from_cache(self, filename, module_name):
paul@0 1054
paul@0 1055
        "Return a module residing in the cache."
paul@0 1056
paul@0 1057
        module = self.modules.get(module_name)
paul@0 1058
paul@12 1059
        if not module and not self.source_is_new(filename, module_name):
paul@13 1060
            module = CachedModule(module_name, self)
paul@12 1061
            self.add_module(module_name, module)
paul@0 1062
paul@12 1063
            filename = join(self.cache, module_name)
paul@12 1064
            self._load(module, module_name, lambda m: m.from_cache, filename)
paul@0 1065
paul@0 1066
        return module
paul@0 1067
paul@12 1068
    def _load(self, module, module_name, fn, filename):
paul@0 1069
paul@0 1070
        """
paul@12 1071
        Load 'module' for the given 'module_name', and with 'fn' performing an
paul@12 1072
        invocation on the module with the given 'filename'.
paul@0 1073
        """
paul@0 1074
paul@12 1075
        # Load the module.
paul@0 1076
paul@0 1077
        if self.verbose:
paul@53 1078
            print >>sys.stderr, module_name in self.required and "Required" or "Loading", module_name, "from", filename
paul@0 1079
        fn(module)(filename)
paul@0 1080
paul@54 1081
        # Add the module object if not already defined.
paul@54 1082
paul@54 1083
        if not self.objects.has_key(module_name):
paul@54 1084
            self.objects[module_name] = Reference("<module>", module_name)
paul@54 1085
paul@0 1086
    def add_module(self, module_name, module):
paul@0 1087
paul@0 1088
        """
paul@0 1089
        Return the module with the given 'module_name', adding a new module
paul@0 1090
        object if one does not already exist.
paul@0 1091
        """
paul@0 1092
paul@0 1093
        self.modules[module_name] = module
paul@12 1094
        if module_name in self.to_import:
paul@12 1095
            self.to_import.remove(module_name)
paul@0 1096
paul@0 1097
# vim: tabstop=4 expandtab shiftwidth=4