# HG changeset patch # User Paul Boddie # Date 1300571162 -3600 # Node ID 96c334ff4431cb3e6bbf5f80b2f8768678d4caa9 # Parent d8329b6ca1cae68c89576ed9fe961946c0c33b12 Added tentative support for tracking attribute assignments together with attribute usage. Added various tests of class attribute assignment which should eventually be supported. Added missing tests. diff -r d8329b6ca1ca -r 96c334ff4431 TO_DO.txt --- a/TO_DO.txt Sun Mar 13 20:58:54 2011 +0100 +++ b/TO_DO.txt Sat Mar 19 22:46:02 2011 +0100 @@ -4,6 +4,18 @@ Consider attribute assignment observations, along with the possibility of class attribute assignment. + Note direct assignments as usual, indirect assignments via the attribute usage + mechanism. During attribute collection and inference, add assigned values to all + inferred targets. + + Since class attributes can be assigned, StoreAttrIndex would no longer need to reject + static attributes, although this might still be necessary where attribute usage analysis + has not been performed. + + Potentially consider changing static attribute details to use object-relative offsets in + order to simplify the instruction implementations. This might allow us to eliminate the + static attribute flag for attributes in the object table, at least at run-time. + Consider attribute usage observations being suspended inside blocks where AttributeError may be caught (although this doesn't anticipate such exceptions being caught outside a function altogether). diff -r d8329b6ca1ca -r 96c334ff4431 micropython/__init__.py --- a/micropython/__init__.py Sun Mar 13 20:58:54 2011 +0100 +++ b/micropython/__init__.py Sat Mar 19 22:46:02 2011 +0100 @@ -37,7 +37,8 @@ which the functionality of the micropython package may be accessed. """ -from micropython.common import ProcessingError, TableGenerationError +from micropython.common import ObjectSet, ProcessingError, TableError, \ + TableGenerationError import micropython.ast import micropython.data import micropython.opt @@ -446,17 +447,18 @@ # Name accounting. - def use_name(self, name, from_name): + def use_name(self, name, from_name, value=None): """ Register the given 'name' as being used in the program from within an - object with the specified 'from_name'. + object with the specified 'from_name'. If the optional 'value' is given, + note an assignment. """ if not self.name_references.has_key(from_name): self.name_references[from_name] = set() - attrnames = (name,) + attrnames = ObjectSet([name]) usage = (attrnames,) self.name_references[from_name].add((None, None, usage)) @@ -604,7 +606,23 @@ for objname, is_static in all_objtypes: for attrnames in usage: - for attrname in attrnames: + for attrname, attrvalues in attrnames.items(): + + # Test for the presence of an attribute on the suggested + # object type. + + try: + attr = objtable.access(objname, attrname) + except TableError: + #print "Warning: object type %r does not support attribute %r" % (objname, attrname) + continue + + # Test for assignment. + + if attrvalues: + parent = attr.parent + for attrvalue in attrvalues: + parent.set(attrname, attrvalue, 0) # Visit attributes of objects known to be used. diff -r d8329b6ca1ca -r 96c334ff4431 micropython/common.py --- a/micropython/common.py Sun Mar 13 20:58:54 2011 +0100 +++ b/micropython/common.py Sat Mar 19 22:46:02 2011 +0100 @@ -3,7 +3,7 @@ """ Common classes. -Copyright (C) 2007, 2008, 2009, 2010 Paul Boddie +Copyright (C) 2007, 2008, 2009, 2010, 2011 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 @@ -26,43 +26,159 @@ except NameError: from sets import Set as set -def merge_set_dicts(dicts): +class ObjectSet: + + "A set of objects with optional associated data." + + def __init__(self, d=None): + if d is None: + self.objects = {} + elif hasattr(d, "items"): + self.objects = dict(d) + else: + self.objects = {} + for key in d: + self.add(key) + + def __repr__(self): + out = ["{"] + first = 1 + for key, value in self.items(): + if not first: + out.append(", ") + else: + first = 0 + out.append(repr(key)) + if value: + out.append(" : ") + out.append(repr(value)) + out.append("}") + return "".join(out) + + def __iter__(self): + return iter(self.keys()) + + # Set membership and comparisons. + + def __hash__(self): + return hash(tuple(self.keys())) + + def cmp(self, other): + return cmp(self.keys(), other.keys()) + + # Set methods. + + def add(self, obj): + if not self.has_key(obj): + self[obj] = [] + + # Dictionary and related methods. + + def __getitem__(self, key): + return self.objects[key] + + def get(self, key, default=None): + return self.objects.get(key, default) + + def __setitem__(self, key, value): + self.objects[key] = value + + def has_key(self, key): + return self.objects.has_key(key) + + def keys(self): + return self.objects.keys() + + def values(self): + return self.objects.values() + + def items(self): + return self.objects.items() + + def update(self, other): + + # Combining dictionary-like objects involves combining values. + + if hasattr(other, "items"): + for key, value in other.items(): + self[key] = value + self.get(key, []) + + # Combining sequence-like objects involves just adding members. + + else: + for key in other: + self.add(key) + + def merge(self, other): + + """ + Merge this object set with an 'other' set, combining the values where + possible, and incorporating values present in only one of the sets. + """ + + merged = ObjectSet() + for key in other.keys(): + if not self.has_key(key): + merged[key] = other[key] + else: + for other_value in other[key]: + for value in self[key]: + merged[key] = value + other_value + + for key in self.keys(): + if not merged.has_key(key): + merged[key] = self[key] + + return merged + +def combine_object_set_lists(l1, l2): + + """ + Combine lists of object sets 'l1' and 'l2' to make a product of their + members. + """ + + combined = [] + for i1 in l1: + for i2 in l2: + combined.append(i1.merge(i2)) + return combined + +def deepen_mapping_dict(d): + + "Convert the values of 'd' to be elements of a potentially larger set." + + new_dict = {} + for key, value in d.items(): + new_dict[key] = set([value]) + return new_dict + +def merge_mapping_dicts(dicts): "Merge the given 'dicts' mapping keys to sets of objects." new_dict = {} - update_set_dict(new_dict, dicts) + update_mapping_dict(new_dict, dicts) return new_dict -def update_set_dict(new_dict, dicts): +def update_mapping_dict(new_dict, dicts): "Update 'new_dict' with the contents of the set dictionary 'dicts'." for old_dict in dicts: - for key, values in old_dict.items(): + for key, value in old_dict.items(): if not new_dict.has_key(key): - new_dict[key] = set(values) + new_dict[key] = ObjectSet(value) else: - new_dict[key].update(values) + new_dict[key].update(value) -def deepen_set_dict(d): +def combine_mapping_dicts(d1, d2): """ - Return a new dictionary mapping keys to sets of tuples of values, using data - from 'd' which is a dictionary mapping keys to sets of values. - """ - - d2 = {} - for key, values in d.items(): - d2[key] = set([tuple(values)]) - return d2 - -def combine_set_dicts(d1, d2): - - """ - Combine dictionaries 'd1' and 'd2' in a resulting dictionary, with the set - values of the contributing dictionaries being merged such that a "product" - of the values for a given key are stored in the combined dictionary. + Combine dictionaries 'd1' and 'd2' in a resulting dictionary, with the + values of the contributing dictionaries being themselves combined such that + a "product" of the values for a given key are stored in the combined + dictionary. """ combined = {} @@ -75,10 +191,7 @@ if d1_values is None: combined[key] = d2[key] else: - combined[key] = set() - for d2_value in d2[key]: - for d1_value in d1_values: - combined[key].add(tuple(set(d1_value).union(d2_value))) + combined[key] = combine_object_set_lists(d1_values, d2[key]) for key in d1.keys(): if key not in d2_keys: diff -r d8329b6ca1ca -r 96c334ff4431 micropython/data.py --- a/micropython/data.py Sun Mar 13 20:58:54 2011 +0100 +++ b/micropython/data.py Sat Mar 19 22:46:02 2011 +0100 @@ -53,8 +53,7 @@ """ from micropython.program import DataObject, DataValue, ReplaceableContext, PlaceholderContext -from micropython.common import AtLeast, InspectError, \ - merge_set_dicts, update_set_dict, deepen_set_dict, combine_set_dicts +from micropython.common import * def shortrepr(obj): if obj is None: @@ -434,7 +433,7 @@ # {(a, b), (e, f)} into a single set {(a, b), (c, d), (e, f)}. contributors, contributed_usage = self.get_usage_from_contributors(contributor) - update_set_dict(contributor_usage, [contributed_usage]) + update_mapping_dict(contributor_usage, [contributed_usage]) # Record all contributors. @@ -446,18 +445,21 @@ # Thus, usage of {(f, g)} combined with {(a, b), (c, d)} would give # {(f, g, a, b), (f, g, c, d)}. - usage = combine_set_dicts(deepen_set_dict(node._attrnames), contributor_usage) + usage = combine_mapping_dicts(deepen_mapping_dict(node._attrnames), contributor_usage) node._attrcontributors = all_contributors node._attrcombined = usage return node._attrcontributors, node._attrcombined - def use_attribute(self, name, attrname): - - "Declare the usage on 'name' of the given 'attrname'." - - return self._use_attribute(name, attrname) + 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): @@ -486,11 +488,12 @@ if importer is not None: importer.use_specific_name(objname, attrname, from_name) - def _use_attribute(self, name, attrname): + 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'. + with the given 'attrname'. If the optional 'value' is specified, an + assignment using the given 'value' is recorded. """ users = self.attribute_users[-1] @@ -499,7 +502,10 @@ if users.has_key(name): for user in users[name]: - user._attrnames[name].add(attrname) + values = user._attrnames[name] + values.add(attrname) + if value is not None: + values[attrname].append(value) return users[name] else: return [] @@ -537,14 +543,14 @@ "Make sure that 'node' is initialised for 'name'." self._init_attribute_user(node) - node._attrnames[name] = set() + node._attrnames[name] = ObjectSet() def _init_attribute_user(self, node): # Attribute usage for names. if not hasattr(node, "_attrnames"): - node._attrnames = {} + node._attrnames = ObjectSet() # Branches contributing usage to this node. @@ -690,7 +696,7 @@ # affected by attribute usage is maintained for the current branch. all_shelved_users = self.attribute_user_shelves.pop() - new_users = merge_set_dicts(all_shelved_users) + new_users = merge_mapping_dicts(all_shelved_users) self.attribute_users[-1] = new_users # Combine the scope usage. @@ -745,7 +751,7 @@ suspended_users = self.suspended_broken_users.pop() current_users = self.attribute_users[-1] - new_users = merge_set_dicts(suspended_users + [current_users]) + new_users = merge_mapping_dicts(suspended_users + [current_users]) self.attribute_users[-1] = new_users def _resume_continuing_branches(self): @@ -765,7 +771,7 @@ # Merge suspended branches with the current branch. - new_users = merge_set_dicts(suspended_users + [current_users]) + new_users = merge_mapping_dicts(suspended_users + [current_users]) self.attribute_users[-1] = new_users # Scope usage methods. diff -r d8329b6ca1ca -r 96c334ff4431 micropython/inspect.py --- a/micropython/inspect.py Sun Mar 13 20:58:54 2011 +0100 +++ b/micropython/inspect.py Sat Mar 19 22:46:02 2011 +0100 @@ -297,18 +297,14 @@ module.set(name, self.expr, 0) - def store_class_attr(self, name): + def store_class_attr(self, name, cls): """ - Record class attribute 'name' in the current class using the current + Record class attribute 'name' in the given class 'cls' using the current expression. """ - if self.in_method and self.namespaces[-2].has_key(name): - self.namespaces[-2].set(name, self.expr, 0) - return 1 - - return 0 + cls.set(name, self.expr, 0) def store_instance_attr(self, name): @@ -327,7 +323,7 @@ return (self.namespaces[-1:] or [self])[0] - def use_name(self, name, node=None): + def use_name(self, name, node=None, value=None): """ Use the given 'name' within the current namespace/unit, either in @@ -336,14 +332,14 @@ """ if node is not None and isinstance(node, compiler.ast.Name): - self.use_attribute(node.name, name) + self.use_attribute(node.name, name, value) # For general name usage, declare usage of the given name from this # particular unit. else: unit = self.get_namespace() - self.importer.use_name(name, unit.full_name()) + self.importer.use_name(name, unit.full_name(), value) # Attribute usage methods. # These are convenience methods which refer to the specific namespace's @@ -385,11 +381,14 @@ self.get_namespace()._define_attribute_user(node) - def use_attribute(self, name, attrname): + def use_attribute(self, name, attrname, value=None): - "Note usage on the attribute user 'name' of the attribute 'attrname'." + """ + Note usage on the attribute user 'name' of the attribute 'attrname', + noting an assignment if 'value' is specified. + """ - return self.get_namespace()._use_attribute(name, attrname) + return self.get_namespace()._use_attribute(name, attrname, value) def use_specific_attribute(self, objname, attrname): @@ -470,17 +469,7 @@ # Note usage of the attribute where a local is involved. - if expr.parent is self.get_namespace(): - - # NOTE: Revisiting of nodes may occur for loops. - - if not hasattr(node, "_attrusers"): - node._attrusers = set() - - node._attrusers.update(self.use_attribute(expr.name, attrname)) - node._username = expr.name - else: - self.use_name(attrname, node.expr) + self._visitAttrUser(expr, attrname, node) elif self.builtins is not None: attr = self.builtins.get(attrname) @@ -492,6 +481,27 @@ return attr + def _visitAttrUser(self, expr, attrname, node, value=None): + + """ + Note usage of the attribute provided by 'expr' with the given 'attrname' + where a local is involved, annotating the given 'node'. If the optional + 'value' is given, note an assignment for future effects on attributes + where such attributes are inferred from the usage. + """ + + if expr.parent is self.get_namespace(): + + # NOTE: Revisiting of nodes may occur for loops. + + if not hasattr(node, "_attrusers"): + node._attrusers = set() + + node._attrusers.update(self.use_attribute(expr.name, attrname, value)) + node._username = expr.name + else: + self.use_name(attrname, node.expr, value) + def _visitFunction(self, node, name): """ @@ -587,28 +597,32 @@ def visitAssAttr(self, node): expr = self.dispatch(node.expr) + attrname = node.attrname # Record the attribute on the presumed target. if isinstance(expr, Attr): + value = expr.get_value() + if expr.name == "self": - if not self.store_class_attr(node.attrname): - self.store_instance_attr(node.attrname) - elif isinstance(expr.get_value(), Module): - self.store_module_attr(node.attrname, expr.get_value()) + self.store_instance_attr(attrname) + + elif isinstance(value, Module): + self.store_module_attr(attrname, value) + self.use_specific_attribute(value.full_name(), attrname) print "Warning: attribute %r of module %r set outside the module." % (node.attrname, expr.get_value().name) + elif isinstance(value, Class): + self.store_class_attr(attrname, value) + self.use_specific_attribute(value.full_name(), attrname) + # Note usage of the attribute where a local is involved. - if expr.parent is self.get_namespace(): - - # NOTE: Revisiting of nodes may occur for loops. + else: + self._visitAttrUser(expr, attrname, node, self.expr) - if not hasattr(node, "_attrusers"): - node._attrusers = set() - - node._attrusers.update(self.use_attribute(expr.name, node.attrname)) - node._username = expr.name + else: + self.use_name(attrname, node) return None diff -r d8329b6ca1ca -r 96c334ff4431 tests/abandoned_attribute_usage.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/abandoned_attribute_usage.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,31 @@ +#!/usr/bin/env python + +""" +This test attempts to cause the recording of the usage of 'C' in the function +'f'. Meanwhile, the methods 'D.g' and 'E.h' should be eliminated. +""" + +class C: + def f(self): + return 1 + +class D: + def g(self): # unused + return 2 + +class E: + def h(self): # unused + return 3 + +def f(c): + if 1: + return c.f() + else: + return 2 + +c = C() +d = D() +e = E() +result1_1 = f(c) + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r d8329b6ca1ca -r 96c334ff4431 tests/attributes_class_assignment.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/attributes_class_assignment.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,13 @@ +#!/usr/bin/env python + +class C: + clsattr = 123 + clsattr2 = 456 + +C.clsattr = 789 +C.clsattr2 = 234 + +result_789 = C.clsattr +result_234 = C.clsattr2 + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r d8329b6ca1ca -r 96c334ff4431 tests/attributes_class_assignment_indirect.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/attributes_class_assignment_indirect.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,14 @@ +#!/usr/bin/env python + +class C: + clsattr = 123 + clsattr2 = 456 + +x = C +x.clsattr = 789 +x.clsattr2 = 234 + +result_789 = C.clsattr +result_234 = C.clsattr2 + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r d8329b6ca1ca -r 96c334ff4431 tests/attributes_class_assignment_unknown.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/attributes_class_assignment_unknown.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,16 @@ +#!/usr/bin/env python + +class C: + clsattr = 123 + clsattr2 = 456 + +def f(cls): + cls.clsattr = 789 + cls.clsattr2 = 234 + +f(C) + +result_789 = C.clsattr +result_234 = C.clsattr2 + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r d8329b6ca1ca -r 96c334ff4431 tests/attributes_class_assignment_unknown_alternatives.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/attributes_class_assignment_unknown_alternatives.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,22 @@ +#!/usr/bin/env python + +class C: + clsattr = 123 + clsattr2 = 456 + +class D: + clsattr = 321 + +def f(cls): + cls.clsattr = 789 + if cls.clsattr: + cls.clsattr2 = 234 + +f(C) +f(D) + +result_789 = C.clsattr +result_234 = C.clsattr2 +result_789 = D.clsattr + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r d8329b6ca1ca -r 96c334ff4431 tests/failure/attribute_access_type_restriction_multiple_candidates.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/failure/attribute_access_type_restriction_multiple_candidates.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,33 @@ +#!/usr/bin/env python + +""" +This test attempts to cause the recording of the usage of 'C' in the function +'f', alongside the expectation that 'D' might be used instead. A guard +stipulating constraints for all of 'f' cannot therefore be generated. Meanwhile, +the method 'E.h' should be eliminated. +""" + +class C: + def f(self): + return 1 + +class D: + def g(self): + return 2 + +class E: + def h(self): # unused + return 3 + +def f(c): + if 1: + if 1: + c.f() # c as C would only succeed if this raised an exception + return c.g() + +c = C() +d = D() +e = E() +result1_1 = f(c) + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r d8329b6ca1ca -r 96c334ff4431 tests/imported_package/__init__.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/imported_package/__init__.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,5 @@ +#!/usr/bin/env python + +attribute = 123 + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r d8329b6ca1ca -r 96c334ff4431 tests/imported_package/module.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/imported_package/module.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,5 @@ +#!/usr/bin/env python + +attribute = 456 + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r d8329b6ca1ca -r 96c334ff4431 tests/importer_package_modules.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/importer_package_modules.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,9 @@ +#!/usr/bin/env python + +import imported_package +import imported_package.module + +result_123 = imported_package.attribute +result_456 = imported_package.module.attribute + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r d8329b6ca1ca -r 96c334ff4431 tests/isinstance.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/isinstance.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,28 @@ +#!/usr/bin/env python + +result_1 = 0 +result_2 = 0 +result_3 = 0 +result_4 = 0 +result_5 = 0 +result_6 = 0 + +if isinstance(1, int): + result_1 = 1 + +if isinstance("", str): + result_2 = 2 + +if isinstance((1, 2, 3), tuple): + result_3 = 3 + +if isinstance((1, 2, 3), (int, tuple)): + result_4 = 4 + +if not isinstance(1, (str, tuple)): + result_5 = 5 + +if isinstance(tuple, type): + result_6 = 6 + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r d8329b6ca1ca -r 96c334ff4431 tests/shadow_class_global.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/shadow_class_global.py Sat Mar 19 22:46:02 2011 +0100 @@ -0,0 +1,12 @@ +#!/usr/bin/env python + +def e(self, x): + return x + +class C: + e = e + +c = C() +result_3 = c.e(3) + +# vim: tabstop=4 expandtab shiftwidth=4