# HG changeset patch # User Paul Boddie # Date 1352157386 -3600 # Node ID a94153ef2e5a51be885d38f507634ca93c28be4f # Parent 83b4c6e5e99b254c7f35378f9ed2dff3f7080209 Moved branch-, attribute usage- and scope-related functionality into the branch module. Made is_method a common namespace method in order to eliminate an isinstance test and the associated import dependency from the attribute usage type deduction code. diff -r 83b4c6e5e99b -r a94153ef2e5a micropython/__init__.py --- a/micropython/__init__.py Tue Nov 06 00:12:46 2012 +0100 +++ b/micropython/__init__.py Tue Nov 06 00:16:26 2012 +0100 @@ -39,6 +39,7 @@ from micropython.data import * from micropython.errors import * +from micropython.objectset import ObjectSet from micropython.program import Location from micropython.types import * import micropython.ast diff -r 83b4c6e5e99b -r a94153ef2e5a micropython/branch.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/micropython/branch.py Tue Nov 06 00:16:26 2012 +0100 @@ -0,0 +1,762 @@ +#!/usr/bin/env python + +""" +Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 Paul Boddie + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; either version 3 of the License, or (at your option) any later +version. + +This program is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +details. + +You should have received a copy of the GNU General Public License along with +this program. If not, see . +""" + +from micropython.errors import * +from micropython.objectset import * +from micropython.types import * + +try: + set +except NameError: + from sets import Set as set + +class AttributeUsage: + + "Management of attribute usage in a program unit." + + def __init__(self): + + # Attributes accessed on objects, potentially narrowing their types. + # Specific namespaces should define known names during initialisation. + # For example, functions can define names belonging to parameters. + + # Attribute users, defining names which use attributes. + + self.attribute_users = [{}] # stack of assignments and branches + + # Define attribute usage to identify active program sections. + # Attribute users are AST nodes defining names. + + self.all_attribute_users = set() + + # Finalisation of a program unit's information. + + def finalise_attribute_usage(self): + + "Propagate attribute usage for the namespace to the importer." + + module = self.module + importer = module and module.importer + + if importer is not None: + + # Visit each user and examine the attribute usage for each name. + + for user in self.all_attribute_users: + + # First, visit the contributors and combine their attribute + # usage with the usage recorded directly on the user. + + self.get_usage_from_contributors(user) + + # Record the defining user on each contributor. + + for contributor in user._attrcontributors: + contributor._attrdefs.append(user) + + # Then, tell the importer about the usage. + + for name in user._attrnames.keys(): + + # Only provide information about names defined by this user. + + usage = user._attrcombined.get(name, []) + + # Skip reporting where no actual usage occurs. + + if usage is None: + continue + + # Eliminate non-usage. + + importer.use_names(user, name, tuple([attrnames for attrnames in usage if attrnames]), self.full_name()) + + def finalise_users(self, objtable): + + "Record the object types for generating guards." + + # Visit each user and examine the attribute usage for each name. + + for user in self.all_attribute_users: + user._attrtypes = self._deduce_types(user._attrcombined, objtable) + self._finalise_contributor(user, objtable) + + def _finalise_contributors(self, node, objtable): + + """ + Visit the contributing branches of 'node', finalising them using the + given 'objtable'. + """ + + for contributor in node._attrbranches: + self._finalise_contributor(contributor, objtable) + + def _finalise_contributor(self, node, objtable): + + """ + Record the specific object types being used in various regions of a + program unit. + """ + + if node._attrspecifictypes is None: + merged = {} + + # Get the combined usage information from the user definitions. + + for user in node._attrdefs or [node]: + + # Filter the usage for each name using the local usage + # information. + + for name, usage in user._attrcombined.items(): + localusage = node._attrnames.get(name) + + if usage and localusage: + if not merged.has_key(name): + merged[name] = ObjectSet() + + for attrnames, value in usage.items(): + if attrnames and localusage.issubset(attrnames): + merged[name][attrnames] = value + + node._attrmerged = merged + node._attrspecifictypes = self._deduce_types(node._attrmerged, objtable) + + self._finalise_contributors(node, objtable) + + def _deduce_types(self, usage, objtable): + + """ + Deduce the types for names from the given attribute 'usage' and using + the given 'objtable'. + """ + + attrtypes = {} + for name, combined_usage in usage.items(): + if combined_usage is not None: + objtypes = get_object_types_for_usage(combined_usage, objtable, name, self.full_name(), True, self.module.importer) + if objtypes: + if self.is_method() and name == "self": + objtypes = filter_using_self(objtypes, self.parent) + attrtypes[name] = objtypes + return attrtypes + + def get_usage_from_contributors(self, node): + + """ + Obtain usage information from the given 'node', combined with usage + details from its contributors, returning a tuple containing a set of all + contributors employed along with a dictionary mapping names to lists of + usage possibilities (each a collection of attribute names). + """ + + unfinished = {} + + # Process any unprocessed contributors, indicating the unfinished state + # of the associated data. + + if node._attrcombined is None: + node._attrcombined = Unset + + for contributor in node._attrbranches: + + # Get contributor details. + + unfinished_contributors = self.get_usage_from_contributors(contributor) + + # Collect unfinished contributors and affected nodes. + + # Where the contributor is already set to Unset, a loop has + # occurred and this node will need to have its usage + # recalculated later for the unfinished contributor. + + if contributor._attrcombined is Unset: + if not unfinished.has_key(contributor): + unfinished[contributor] = [] + unfinished[contributor].append(node) + continue + + # Where the contributor provides usage details, it may also + # communicate unfinished contributor information. As a + # consequence, this node is also affected. + + for unfinished_contributor, nodes in unfinished_contributors.items(): + if not unfinished.has_key(unfinished_contributor): + unfinished[unfinished_contributor] = nodes + else: + unfinished[unfinished_contributor] += nodes + + if node not in unfinished[unfinished_contributor]: + unfinished[unfinished_contributor].append(node) + + # Set the current state of the usage on this node. + + node._attrcombined, node._attrcontributors = \ + self.get_usage_from_contributors_for_node(node) + + # Complete unfinished contributors relying on this node. + + if unfinished.has_key(node): + processed = set() + for contributor in unfinished[node]: + if not contributor in processed: + processed.add(contributor) + + contributor._attrcombined, contributor._attrcontributors = \ + self.get_usage_from_contributors_for_node(contributor) + + del unfinished[node] + + return unfinished + + def get_usage_from_contributors_for_node(self, node): + + # Visit each contributor, gathering usage for each name. + + contributor_usage = {} + all_contributions = [] + all_contributors = set() + + for contributor in node._attrbranches: + usage = contributor._attrcombined + if usage is not Unset: + all_contributions.append(usage) + + all_contributors.add(contributor) + contributors = contributor._attrcontributors + if contributors is not None: + all_contributors.update(contributors) + + # Get contributed usage for each contributor. + # This gathers usage for each name such as {(a, b), (c, d)} and + # {(a, b), (e, f)} into a single set {(a, b), (c, d), (e, f)}. + + update_mapping_dict(contributor_usage, all_contributions) + + # Then get the resulting usage. + # First, make the current usage compatible with the contributed + # usage: this makes the attribute usage for each name merely one + # member in a list of many possibilities. + # Then, combine the current usage with the contributed usage. + # Thus, usage of {(f, g)} combined with {(a, b), (c, d)} would give + # {(f, g, a, b), (f, g, c, d)}. + + return combine_mapping_dicts(deepen_mapping_dict(node._attrnames), contributor_usage), all_contributors + + # Attribute usage methods. + + def use_attribute(self, name, attrname, value=None): + + """ + Note usage on the attribute user 'name' of the attribute 'attrname', + noting an assignment if 'value' is specified. + """ + + return self._use_attribute(name, attrname, value) + + def use_specific_attribute(self, objname, attrname): + + "Declare the usage on 'objname' of the given 'attrname'." + + self._use_specific_attribute(objname, attrname) + + # These shadow various methods in the InspectedModule class, and provide + # implementations generally. + + def _use_specific_attribute(self, objname, attrname, from_name=None): + + """ + Note attribute usage specifically on 'objname' - an object which is + known at inspection time - or in the current unit if 'objname' is None, + nominating a specific attribute 'attrname'. + + This bypasses attribute user mechanisms. + """ + + from_name = from_name or self.full_name() + objname = objname or from_name + module = self.module + importer = module and module.importer + + if importer is not None: + importer.use_specific_name(objname, attrname, from_name) + + def _use_attribute(self, name, attrname, value=None): + + """ + Indicate the use of the given 'name' in this namespace of an attribute + with the given 'attrname'. If the optional 'value' is specified, an + assignment using the given 'value' is recorded. + """ + + users = self.attribute_users[-1] + + # If no users are defined for the name, it cannot be handled. + + if not users.has_key(name): + return [] + + # Add the usage to all current users. + + for user in users[name]: + values = user._attrnames[name] + if values is None: + values = user._attrnames[name] = ObjectSet() + + # Add an entry for the attribute, optionally with an assigned + # value. + + values.add(attrname) + if value is not None: + values[attrname].add(value) + + return users[name] + + def _define_attribute_user(self, node): + + """ + Define 'node' as the user of attributes, indicating the point where the + user is defined. + """ + + name = node.name + self._define_attribute_user_for_name(node, name) + + def _define_attribute_user_for_name(self, node, name): + + "Define 'node' as the user of attributes for the given 'name'." + + users = self.attribute_users[-1] + + # This node overrides previous definitions. + + users[name] = set([node]) + + # Record the attribute combinations for the name. + + self._init_attribute_user_for_name(node, name) + + # Remember this user. + + self.all_attribute_users.add(node) + + def _init_attribute_user_for_name(self, node, name): + + "Make sure that 'node' is initialised for 'name'." + + self._init_attribute_user(node) + node._attrnames[name] = None + + def _init_attribute_user(self, node): + + # Attribute usage for names. + + if node._attrnames is None: + node._attrnames = {} + node._attrmerged = {} + + # Branches contributing usage to this node. + + if node._attrbranches is None: + node._attrbranches = [] + + # Definitions receiving usage from this node. + + if node._attrdefs is None: + node._attrdefs = [] + + def _define_attribute_accessor(self, name, attrname, node, value): + + # NOTE: Revisiting of nodes may occur for loops. + + if node._attrusers is None: + node._attrusers = set() + + node._attrusers.update(self.use_attribute(name, attrname, value)) + node._username = name + +class ScopeUsage: + + "Scope usage tracking." + + def __init__(self): + + # Scope usage, indicating the origin of names. + + self.scope_usage = [{}] # stack of scope usage + + def define_scope(self, name, scope): + + """ + Define 'name' as being from the given 'scope' in the current namespace. + """ + + self.scope_usage[-1][name] = scope + + def note_scope(self, name, scope): + + """ + Note usage of 'name' from the given 'scope' in the current namespace. + If a conflict has been recorded previously, raise an exception. + """ + + scope_usage = self.scope_usage[-1] + + if scope_usage.has_key(name): + found_scope = scope_usage[name] + if isinstance(found_scope, ScopeConflict): + raise InspectError("Scope conflict for %r: defined as %s." % ( + name, ", ".join(found_scope.scopes))) + + scope_usage[name] = scope + + def used_in_scope(self, name, scope): + + """ + Return whether 'name' is used from the given 'scope' in the current + namespace. + """ + + scope_usage = self.scope_usage[-1] + return scope_usage.get(name) == scope + +class BranchTracking(AttributeUsage, ScopeUsage): + + """ + Management of branches, relying on attribute usage support. + """ + + def __init__(self): + AttributeUsage.__init__(self) + ScopeUsage.__init__(self) + + # Details of attribute users at each active branch level. + + self.attribute_user_shelves = [] + + # Details of name scopes at each active branch level. + + self.scope_shelves = [] + + # Suspended user details plus loop details. + + self.suspended_broken_users = [] # stack of lists of user dicts + self.suspended_continuing_users = [] # stack of lists of user dicts + + # Abandoned usage, useful for reviving usage for exception handlers. + + self.abandoned_users = [[]] # stack of lists of users + + # Methods shadowing the convenience methods provided during inspection. + + def _new_branchpoint(self, loop_node=None): + + """ + Establish a new branchpoint where several control-flow branches diverge + and subsequently converge. + """ + + self.attribute_user_shelves.append([]) + self.scope_shelves.append([]) + + if loop_node is not None: + self.suspended_broken_users.append([]) + self.suspended_continuing_users.append((loop_node, [])) + + def _new_branch(self, node): + + """ + Establish a new control-flow branch, transferring attribute usage to + the new branch so that it may be augmented for each name locally. + + Add the given 'node' as an active user to be informed of attribute + usage. + """ + + attribute_users = self.attribute_users[-1] + + # Define this node as the active attribute user for all currently + # defined names. + + new_users = {} + + for name in attribute_users.keys(): + new_users[name] = [node] + self._init_attribute_user_for_name(node, name) + + self._init_attribute_user(node) + self.attribute_users.append(new_users) + + # Add this user as a contributor to the previously active users. + + self._connect_users_to_branch(attribute_users, node) + + # Retain a record of scope usage. + + scope_usage = {} + scope_usage.update(self.scope_usage[-1]) + self.scope_usage.append(scope_usage) + + # Retain a record of abandoned branch users. + + self.abandoned_users.append([]) + + def _connect_users_to_branch(self, attribute_users, node): + + """ + Given the 'attribute_users' mapping, connect the users referenced in the + mapping to the given branch 'node'. + """ + + all_users = set() + + for users in attribute_users.values(): + all_users.update(users) + + for user in all_users: + self._init_attribute_user(user) + user._attrbranches.append(node) + + def _abandon_branch(self, retain_branch=True): + + """ + Abandon scope usage, permitting locally different scopes for names, + provided these cannot "escape" from the branch. + """ + + attribute_users = self.attribute_users[-1] + + self.attribute_users[-1] = {} + self.scope_usage[-1] = abandoned_branch_scope + + if retain_branch: + self.abandoned_users[-1].append(attribute_users) + + def _suspend_broken_branch(self): + + """ + Suspend a branch for resumption after the current loop. + """ + + attribute_users = self.attribute_users[-1] + + users = self.suspended_broken_users[-1] + users.append(attribute_users) + self._abandon_branch(False) + + def _suspend_continuing_branch(self): + + """ + Suspend a branch for resumption after the current iteration. + """ + + attribute_users = self.attribute_users[-1] + + loop_node, users = self.suspended_continuing_users[-1] + users.append(attribute_users) + self._abandon_branch(False) + + def _shelve_branch(self): + + """ + Shelve the current control-flow branch, recording the attribute usage + for subsequent merging. If this branch should be abandoned, the usage + observations are still recorded but will not contribute to subsequent + observations after a merge. + """ + + users = self.attribute_users.pop() + self.attribute_user_shelves[-1].append(users) + + scope_usage = self.scope_usage.pop() + self.scope_shelves[-1].append(scope_usage) + + def _merge_branches(self): + + """ + Merge control-flow branches. This should find the users active within + each branch, which have been "shelved", and update the active users + dictionary with these contributions. + """ + + # Combine the attribute users. This ensures that a list of users + # affected by attribute usage is maintained for the current branch. + + all_shelved_users = self.attribute_user_shelves.pop() + new_users = merge_mapping_dicts(all_shelved_users) + self.attribute_users[-1] = new_users + + # Abandoned users are retained for exception handling purposes. + + all_abandoned_users = self.abandoned_users.pop() + new_abandoned_users = merge_mapping_dicts(all_abandoned_users) + self.abandoned_users[-1].append(new_abandoned_users) + + # Combine the scope usage. + + scope_usage = self.scope_usage[-1] + new_scope_usage = {} + + all_scope_usage = self.scope_shelves.pop() + all_scope_names = set() + + # Find all the names for whom scope information has been defined. + + for shelved_usage in all_scope_usage: + all_scope_names.update(shelved_usage.keys()) + + for shelved_usage in all_scope_usage: + for name in all_scope_names: + + # Find the recorded scope for the name. + + if shelved_usage.has_key(name): + scope = shelved_usage[name] + elif scope_usage.has_key(name): + scope = scope_usage[name] + + # For abandoned branches, no scope is asserted for a name. + + elif isinstance(shelved_usage, AbandonedBranchScope): + scope = None + + # If no scope is recorded, find a suitable external source. + + else: + attr, scope, full_name = self._get_with_scope(name, external=1) + + # Attempt to record the scope, testing for conflicts. + + if scope: + if not new_scope_usage.has_key(name): + new_scope_usage[name] = scope + else: + new_scope = new_scope_usage[name] + if new_scope != scope: + if isinstance(new_scope, ScopeConflict): + if isinstance(scope, ScopeConflict): + scopes = scope.scopes.union(new_scope.scopes) + else: + scopes = new_scope.scopes.union(set([scope])) + elif isinstance(scope, ScopeConflict): + scopes = scope.scopes.union(set([new_scope])) + else: + scopes = set([scope, new_scope]) + new_scope_usage[name] = ScopeConflict(scopes) + + self.scope_usage[-1] = new_scope_usage + + def _resume_broken_branches(self): + + """ + Incorporate users from suspended broken branches into the current set of + active users. + """ + + suspended_users = self.suspended_broken_users.pop() + current_users = self.attribute_users[-1] + new_users = merge_mapping_dicts(suspended_users + [current_users]) + self.attribute_users[-1] = new_users + + def _resume_continuing_branches(self): + + """ + Incorporate users from suspended continuing branches into the current + set of active users, merging usage from the latter with the former. + """ + + loop_node, suspended_users = self.suspended_continuing_users.pop() + current_users = self.attribute_users[-1] + + # Connect the suspended users to the loop node. + + for users in suspended_users: + self._connect_users_to_branch(users, loop_node) + + # Merge suspended branches with the current branch. + + new_users = merge_mapping_dicts(suspended_users + [current_users]) + self.attribute_users[-1] = new_users + + def _resume_abandoned_branches(self): + + """ + Incorporate users from abandoned branches into the current set of active + users. The abandoned branches are taken from the containing branch. + """ + + current_users = self.attribute_users[-1] + abandoned_users = self.abandoned_users[-2] + new_users = merge_mapping_dicts(abandoned_users + [current_users]) + self.attribute_users[-1] = new_users + +# Special helper classes for usage and scope resolution. + +class EmptyDict: + + "A class providing dictionaries which retain no information." + + def has_key(self, name): + return False + + def __setitem__(self, name, value): + pass + + def __getitem__(self, name): + raise KeyError, name + + def get(self, name, default=None): + return default + + def keys(self): + return [] + + values = items = keys + +class AbandonedBranchScope(EmptyDict): + + """ + A class providing a value or state for an abandoned branch distinct from an + empty scope dictionary. + """ + + pass + +abandoned_branch_scope = AbandonedBranchScope() + +class ScopeConflict: + + """ + A scope conflict caused when different code branches contribute different + sources of names. + """ + + def __init__(self, scopes): + self.scopes = scopes + +class UnsetType: + + "A None-like value." + + def __nonzero__(self): + return False + +Unset = UnsetType() + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r 83b4c6e5e99b -r a94153ef2e5a micropython/data.py --- a/micropython/data.py Tue Nov 06 00:12:46 2012 +0100 +++ b/micropython/data.py Tue Nov 06 00:16:26 2012 +0100 @@ -52,12 +52,9 @@ where each such object is defined. """ -from compiler.ast import AttributeUser from micropython.program import ReplaceableContext, PlaceholderContext from micropython.basicdata import * -from micropython.errors import * -from micropython.objectset import * -from micropython.types import * +from micropython.branch import BranchTracking import sys try: @@ -65,45 +62,19 @@ except NameError: from sets import Set as set -class NamespaceDict(Namespace): +class NamespaceDict(Namespace, BranchTracking): "A mix-in providing dictionary methods." def __init__(self, module=None): + BranchTracking.__init__(self) + self.module = module self.namespace = {} self.globals = set() self.lambdas = {} # only really useful for functions self.finalised = False - # Attributes accessed on objects, potentially narrowing their types. - # Specific namespaces should define known names during initialisation. - # For example, functions can define names belonging to parameters. - - # Attribute users, defining names which use attributes. - - self.attribute_users = [{}] # stack of assignments and branches - self.attribute_user_shelves = [] - - # Suspended user details plus loop details. - - self.suspended_broken_users = [] # stack of lists of user dicts - self.suspended_continuing_users = [] # stack of lists of user dicts - - # Scope usage, indicating the origin of names. - - self.scope_usage = [{}] # stack of scope usage - self.scope_shelves = [] - - # Abandoned usage, useful for reviving usage for exception handlers. - - self.abandoned_users = [[]] # stack of lists of users - - # Define attribute usage to identify active program sections. - # Attribute users are AST nodes defining names. - - self.all_attribute_users = set() - # Attribute/name definition and access. def __delitem__(self, name): @@ -127,6 +98,16 @@ def get(self, name, default=None): return self.namespace.get(name, default) + # Introspection methods. + + def is_method(self): + + """ + Return whether this function is a method explicitly defined in a class. + """ + + return False + # Administrative methods. def finalise(self, objtable): @@ -356,680 +337,6 @@ self.finalised = False - # Attribute usage methods. - - def finalise_attribute_usage(self): - - "Propagate attribute usage for the namespace to the importer." - - module = self.module - importer = module and module.importer - - if importer is not None: - - # Visit each user and examine the attribute usage for each name. - - for user in self.all_attribute_users: - - # First, visit the contributors and combine their attribute - # usage with the usage recorded directly on the user. - - self.get_usage_from_contributors(user) - - # Record the defining user on each contributor. - - for contributor in user._attrcontributors: - contributor._attrdefs.append(user) - - # Then, tell the importer about the usage. - - for name in user._attrnames.keys(): - - # Only provide information about names defined by this user. - - usage = user._attrcombined.get(name, []) - - # Skip reporting where no actual usage occurs. - - if usage is None: - continue - - # Eliminate non-usage. - - importer.use_names(user, name, tuple([attrnames for attrnames in usage if attrnames]), self.full_name()) - - def finalise_users(self, objtable): - - "Record the object types for generating guards." - - # Visit each user and examine the attribute usage for each name. - - for user in self.all_attribute_users: - user._attrtypes = self._deduce_types(user._attrcombined, objtable) - self._finalise_contributor(user, objtable) - - def _finalise_contributors(self, node, objtable): - - """ - Visit the contributing branches of 'node', finalising them using the - given 'objtable'. - """ - - for contributor in node._attrbranches: - self._finalise_contributor(contributor, objtable) - - def _finalise_contributor(self, node, objtable): - - """ - Record the specific object types being used in various regions of a - program unit. - """ - - if node._attrspecifictypes is None: - merged = {} - - # Get the combined usage information from the user definitions. - - for user in node._attrdefs or [node]: - - # Filter the usage for each name using the local usage - # information. - - for name, usage in user._attrcombined.items(): - localusage = node._attrnames.get(name) - - if usage and localusage: - if not merged.has_key(name): - merged[name] = ObjectSet() - - for attrnames, value in usage.items(): - if attrnames and localusage.issubset(attrnames): - merged[name][attrnames] = value - - node._attrmerged = merged - node._attrspecifictypes = self._deduce_types(node._attrmerged, objtable) - - self._finalise_contributors(node, objtable) - - def _deduce_types(self, usage, objtable): - - """ - Deduce the types for names from the given attribute 'usage' and using - the given 'objtable'. - """ - - attrtypes = {} - for name, combined_usage in usage.items(): - if combined_usage is not None: - objtypes = get_object_types_for_usage(combined_usage, objtable, name, self.full_name(), True, self.module.importer) - if objtypes: - if isinstance(self, Function) and self.is_method() and name == "self": - objtypes = filter_using_self(objtypes, self.parent) - attrtypes[name] = objtypes - return attrtypes - - def get_usage_from_contributors(self, node): - - """ - Obtain usage information from the given 'node', combined with usage - details from its contributors, returning a tuple containing a set of all - contributors employed along with a dictionary mapping names to lists of - usage possibilities (each a collection of attribute names). - """ - - unfinished = {} - - # Process any unprocessed contributors, indicating the unfinished state - # of the associated data. - - if node._attrcombined is None: - node._attrcombined = Unset - - for contributor in node._attrbranches: - - # Get contributor details. - - unfinished_contributors = self.get_usage_from_contributors(contributor) - - # Collect unfinished contributors and affected nodes. - - # Where the contributor is already set to Unset, a loop has - # occurred and this node will need to have its usage - # recalculated later for the unfinished contributor. - - if contributor._attrcombined is Unset: - if not unfinished.has_key(contributor): - unfinished[contributor] = [] - unfinished[contributor].append(node) - continue - - # Where the contributor provides usage details, it may also - # communicate unfinished contributor information. As a - # consequence, this node is also affected. - - for unfinished_contributor, nodes in unfinished_contributors.items(): - if not unfinished.has_key(unfinished_contributor): - unfinished[unfinished_contributor] = nodes - else: - unfinished[unfinished_contributor] += nodes - - if node not in unfinished[unfinished_contributor]: - unfinished[unfinished_contributor].append(node) - - # Set the current state of the usage on this node. - - node._attrcombined, node._attrcontributors = \ - self.get_usage_from_contributors_for_node(node) - - # Complete unfinished contributors relying on this node. - - if unfinished.has_key(node): - processed = set() - for contributor in unfinished[node]: - if not contributor in processed: - processed.add(contributor) - - contributor._attrcombined, contributor._attrcontributors = \ - self.get_usage_from_contributors_for_node(contributor) - - del unfinished[node] - - return unfinished - - def get_usage_from_contributors_for_node(self, node): - - # Visit each contributor, gathering usage for each name. - - contributor_usage = {} - all_contributions = [] - all_contributors = set() - - for contributor in node._attrbranches: - usage = contributor._attrcombined - if usage is not Unset: - all_contributions.append(usage) - - all_contributors.add(contributor) - contributors = contributor._attrcontributors - if contributors is not None: - all_contributors.update(contributors) - - # Get contributed usage for each contributor. - # This gathers usage for each name such as {(a, b), (c, d)} and - # {(a, b), (e, f)} into a single set {(a, b), (c, d), (e, f)}. - - update_mapping_dict(contributor_usage, all_contributions) - - # Then get the resulting usage. - # First, make the current usage compatible with the contributed - # usage: this makes the attribute usage for each name merely one - # member in a list of many possibilities. - # Then, combine the current usage with the contributed usage. - # Thus, usage of {(f, g)} combined with {(a, b), (c, d)} would give - # {(f, g, a, b), (f, g, c, d)}. - - return combine_mapping_dicts(deepen_mapping_dict(node._attrnames), contributor_usage), all_contributors - - def use_attribute(self, name, attrname, value=None): - - """ - Note usage on the attribute user 'name' of the attribute 'attrname', - noting an assignment if 'value' is specified. - """ - - return self._use_attribute(name, attrname, value) - - def use_specific_attribute(self, objname, attrname): - - "Declare the usage on 'objname' of the given 'attrname'." - - self._use_specific_attribute(objname, attrname) - - # These shadow various methods in the InspectedModule class, and provide - # implementations generally. - - def _use_specific_attribute(self, objname, attrname, from_name=None): - - """ - Note attribute usage specifically on 'objname' - an object which is - known at inspection time - or in the current unit if 'objname' is None, - nominating a specific attribute 'attrname'. - - This bypasses attribute user mechanisms. - """ - - from_name = from_name or self.full_name() - objname = objname or from_name - module = self.module - importer = module and module.importer - - if importer is not None: - importer.use_specific_name(objname, attrname, from_name) - - def _use_attribute(self, name, attrname, value=None): - - """ - Indicate the use of the given 'name' in this namespace of an attribute - with the given 'attrname'. If the optional 'value' is specified, an - assignment using the given 'value' is recorded. - """ - - users = self.attribute_users[-1] - - # If no users are defined for the name, it cannot be handled. - - if not users.has_key(name): - return [] - - # Add the usage to all current users. - - for user in users[name]: - values = user._attrnames[name] - if values is None: - values = user._attrnames[name] = ObjectSet() - - # Add an entry for the attribute, optionally with an assigned - # value. - - values.add(attrname) - if value is not None: - values[attrname].add(value) - - return users[name] - - def _define_attribute_user(self, node): - - """ - Define 'node' as the user of attributes, indicating the point where the - user is defined. - """ - - name = node.name - self._define_attribute_user_for_name(node, name) - - def _define_attribute_user_for_name(self, node, name): - - "Define 'node' as the user of attributes for the given 'name'." - - users = self.attribute_users[-1] - - # This node overrides previous definitions. - - users[name] = set([node]) - - # Record the attribute combinations for the name. - - self._init_attribute_user_for_name(node, name) - - # Remember this user. - - self.all_attribute_users.add(node) - - def _init_attribute_user_for_name(self, node, name): - - "Make sure that 'node' is initialised for 'name'." - - self._init_attribute_user(node) - node._attrnames[name] = None - - def _init_attribute_user(self, node): - - # Attribute usage for names. - - if node._attrnames is None: - node._attrnames = {} - node._attrmerged = {} - - # Branches contributing usage to this node. - - if node._attrbranches is None: - node._attrbranches = [] - - # Definitions receiving usage from this node. - - if node._attrdefs is None: - node._attrdefs = [] - - def _define_attribute_accessor(self, name, attrname, node, value): - - # NOTE: Revisiting of nodes may occur for loops. - - if node._attrusers is None: - node._attrusers = set() - - node._attrusers.update(self.use_attribute(name, attrname, value)) - node._username = name - - # Branch management methods. - - def _new_branchpoint(self, loop_node=None): - - """ - Establish a new branchpoint where several control-flow branches diverge - and subsequently converge. - """ - - self.attribute_user_shelves.append([]) - self.scope_shelves.append([]) - - if loop_node is not None: - self.suspended_broken_users.append([]) - self.suspended_continuing_users.append((loop_node, [])) - - def _new_branch(self, node): - - """ - Establish a new control-flow branch, transferring attribute usage to - the new branch so that it may be augmented for each name locally. - - Add the given 'node' as an active user to be informed of attribute - usage. - """ - - attribute_users = self.attribute_users[-1] - - # Define this node as the active attribute user for all currently - # defined names. - - new_users = {} - - for name in attribute_users.keys(): - new_users[name] = [node] - self._init_attribute_user_for_name(node, name) - - self._init_attribute_user(node) - self.attribute_users.append(new_users) - - # Add this user as a contributor to the previously active users. - - self._connect_users_to_branch(attribute_users, node) - - # Retain a record of scope usage. - - scope_usage = {} - scope_usage.update(self.scope_usage[-1]) - self.scope_usage.append(scope_usage) - - # Retain a record of abandoned branch users. - - self.abandoned_users.append([]) - - def _connect_users_to_branch(self, attribute_users, node): - - """ - Given the 'attribute_users' mapping, connect the users referenced in the - mapping to the given branch 'node'. - """ - - all_users = set() - - for users in attribute_users.values(): - all_users.update(users) - - for user in all_users: - self._init_attribute_user(user) - user._attrbranches.append(node) - - def _abandon_branch(self, retain_branch=True): - - """ - Abandon scope usage, permitting locally different scopes for names, - provided these cannot "escape" from the branch. - """ - - attribute_users = self.attribute_users[-1] - - self.attribute_users[-1] = {} - self.scope_usage[-1] = abandoned_branch_scope - - if retain_branch: - self.abandoned_users[-1].append(attribute_users) - - def _suspend_broken_branch(self): - - """ - Suspend a branch for resumption after the current loop. - """ - - attribute_users = self.attribute_users[-1] - - users = self.suspended_broken_users[-1] - users.append(attribute_users) - self._abandon_branch(False) - - def _suspend_continuing_branch(self): - - """ - Suspend a branch for resumption after the current iteration. - """ - - attribute_users = self.attribute_users[-1] - - loop_node, users = self.suspended_continuing_users[-1] - users.append(attribute_users) - self._abandon_branch(False) - - def _shelve_branch(self): - - """ - Shelve the current control-flow branch, recording the attribute usage - for subsequent merging. If this branch should be abandoned, the usage - observations are still recorded but will not contribute to subsequent - observations after a merge. - """ - - users = self.attribute_users.pop() - self.attribute_user_shelves[-1].append(users) - - scope_usage = self.scope_usage.pop() - self.scope_shelves[-1].append(scope_usage) - - def _merge_branches(self): - - """ - Merge control-flow branches. This should find the users active within - each branch, which have been "shelved", and update the active users - dictionary with these contributions. - """ - - # Combine the attribute users. This ensures that a list of users - # affected by attribute usage is maintained for the current branch. - - all_shelved_users = self.attribute_user_shelves.pop() - new_users = merge_mapping_dicts(all_shelved_users) - self.attribute_users[-1] = new_users - - # Abandoned users are retained for exception handling purposes. - - all_abandoned_users = self.abandoned_users.pop() - new_abandoned_users = merge_mapping_dicts(all_abandoned_users) - self.abandoned_users[-1].append(new_abandoned_users) - - # Combine the scope usage. - - scope_usage = self.scope_usage[-1] - new_scope_usage = {} - - all_scope_usage = self.scope_shelves.pop() - all_scope_names = set() - - # Find all the names for whom scope information has been defined. - - for shelved_usage in all_scope_usage: - all_scope_names.update(shelved_usage.keys()) - - for shelved_usage in all_scope_usage: - for name in all_scope_names: - - # Find the recorded scope for the name. - - if shelved_usage.has_key(name): - scope = shelved_usage[name] - elif scope_usage.has_key(name): - scope = scope_usage[name] - - # For abandoned branches, no scope is asserted for a name. - - elif isinstance(shelved_usage, AbandonedBranchScope): - scope = None - - # If no scope is recorded, find a suitable external source. - - else: - attr, scope, full_name = self._get_with_scope(name, external=1) - - # Attempt to record the scope, testing for conflicts. - - if scope: - if not new_scope_usage.has_key(name): - new_scope_usage[name] = scope - else: - new_scope = new_scope_usage[name] - if new_scope != scope: - if isinstance(new_scope, ScopeConflict): - if isinstance(scope, ScopeConflict): - scopes = scope.scopes.union(new_scope.scopes) - else: - scopes = new_scope.scopes.union(set([scope])) - elif isinstance(scope, ScopeConflict): - scopes = scope.scopes.union(set([new_scope])) - else: - scopes = set([scope, new_scope]) - new_scope_usage[name] = ScopeConflict(scopes) - - self.scope_usage[-1] = new_scope_usage - - def _resume_broken_branches(self): - - """ - Incorporate users from suspended broken branches into the current set of - active users. - """ - - suspended_users = self.suspended_broken_users.pop() - current_users = self.attribute_users[-1] - new_users = merge_mapping_dicts(suspended_users + [current_users]) - self.attribute_users[-1] = new_users - - def _resume_continuing_branches(self): - - """ - Incorporate users from suspended continuing branches into the current - set of active users, merging usage from the latter with the former. - """ - - loop_node, suspended_users = self.suspended_continuing_users.pop() - current_users = self.attribute_users[-1] - - # Connect the suspended users to the loop node. - - for users in suspended_users: - self._connect_users_to_branch(users, loop_node) - - # Merge suspended branches with the current branch. - - new_users = merge_mapping_dicts(suspended_users + [current_users]) - self.attribute_users[-1] = new_users - - def _resume_abandoned_branches(self): - - """ - Incorporate users from abandoned branches into the current set of active - users. The abandoned branches are taken from the containing branch. - """ - - current_users = self.attribute_users[-1] - abandoned_users = self.abandoned_users[-2] - new_users = merge_mapping_dicts(abandoned_users + [current_users]) - self.attribute_users[-1] = new_users - - # Scope usage methods. - - def define_scope(self, name, scope): - - """ - Define 'name' as being from the given 'scope' in the current namespace. - """ - - self.scope_usage[-1][name] = scope - - def note_scope(self, name, scope): - - """ - Note usage of 'name' from the given 'scope' in the current namespace. - If a conflict has been recorded previously, raise an exception. - """ - - scope_usage = self.scope_usage[-1] - - if scope_usage.has_key(name): - found_scope = scope_usage[name] - if isinstance(found_scope, ScopeConflict): - raise InspectError("Scope conflict for %r: defined as %s." % ( - name, ", ".join(found_scope.scopes))) - - scope_usage[name] = scope - - def used_in_scope(self, name, scope): - - """ - Return whether 'name' is used from the given 'scope' in the current - namespace. - """ - - scope_usage = self.scope_usage[-1] - return scope_usage.get(name) == scope - -# Special helper classes for usage and scope resolution. - -class EmptyDict: - - "A class providing dictionaries which retain no information." - - def has_key(self, name): - return False - - def __setitem__(self, name, value): - pass - - def __getitem__(self, name): - raise KeyError, name - - def get(self, name, default=None): - return default - - def keys(self): - return [] - - values = items = keys - -class AbandonedBranchScope(EmptyDict): - - """ - A class providing a value or state for an abandoned branch distinct from an - empty scope dictionary. - """ - - pass - -abandoned_branch_scope = AbandonedBranchScope() - -class ScopeConflict: - - """ - A scope conflict caused when different code branches contribute different - sources of names. - """ - - def __init__(self, scopes): - self.scopes = scopes - -class NullBranch(AttributeUser): - - "A class representing an attribute user for a non-existent branch." - - pass - # Program data structures. class Attr: @@ -2227,13 +1534,4 @@ def __repr__(self): return "AtLeast(%r)" % self.count -class UnsetType: - - "A None-like value." - - def __nonzero__(self): - return False - -Unset = UnsetType() - # vim: tabstop=4 expandtab shiftwidth=4 diff -r 83b4c6e5e99b -r a94153ef2e5a micropython/inspect.py --- a/micropython/inspect.py Tue Nov 06 00:12:46 2012 +0100 +++ b/micropython/inspect.py Tue Nov 06 00:16:26 2012 +0100 @@ -78,6 +78,12 @@ import compiler.ast import sys +class NullBranch(compiler.ast.AttributeUser): + + "A class representing an attribute user for a non-existent branch." + + pass + # Program visitors. class InspectedModule(ASTVisitor, Module):