# HG changeset patch # User Paul Boddie # Date 1366906112 -7200 # Node ID 4d49311d36595c87f019d99e4fb7816ee885ae74 # Parent bdc835dee81d84a3fadb5c8b73906b9ab0b73c03 Added a separate deduction process, simplifying the syspython code generation for attribute access and assignment. Ultimately, report generation should also benefit from the separate deduction process. Added the deduction stage and support for syspython generation to the test program. diff -r bdc835dee81d -r 4d49311d3659 docs/annotations.txt --- a/docs/annotations.txt Sat Apr 20 00:59:58 2013 +0200 +++ b/docs/annotations.txt Thu Apr 25 18:08:32 2013 +0200 @@ -3,6 +3,32 @@ These annotations are defined in the revised compiler.ast classes. +Deduction Results +----------------- + +_access_type defines the kind of access involved for a particular node + and determines which of the following annotations will be + employed +_value_deduced defines a specific result associated with an attribute + access during deduction and based on inspection results +_attr_deduced defines an attribute result according to deduction based + on inspection results, with the accessor being the parent + defined in this object for static attributes +_position_deduced defines a common position employed by all deduced + attributes for an access operation which is relative to + the accessor evaluated at run time +_set_context indicates the deduced effect on the context in an access + operation, whether the context would be replaced + unconditionally or conditionally + +_attrs_deduced_from_usage +_attrs_deduced + provided as additional annotations more suitable for + report generation than code generation, since they + describe a range of deduced attributes for a given node, + but such ranges may not lend themselves to the generation + of optimised code + Evaluation Results ------------------ diff -r bdc835dee81d -r 4d49311d3659 micropython/common.py --- a/micropython/common.py Sat Apr 20 00:59:58 2013 +0200 +++ b/micropython/common.py Thu Apr 25 18:08:32 2013 +0200 @@ -76,6 +76,42 @@ # Deduction-related methods. + def get_attributes(self, targets, attrname): + + "Return a list of attributes for 'targets' supporting 'attrname'." + + attributes = set() + + for target in targets: + try: + attributes.add(self.objtable.access(target.full_name(), attrname)) + except TableError: + return None + + return attributes + + def get_attribute_and_value(self, obj): + + """ + Return (attribute, value) details for the given 'obj', where an + attribute of None can be returned for constant objects, and where None + can be returned as the result where no concrete details can be provided. + """ + + if isinstance(obj, Constant): + return None, obj + + if isinstance(obj, Attr): + return obj, obj.get_value() + + return None + + def provides_constant_result(self, value): + + "Return whether 'value' provides a constant result." + + return isinstance(value, (Const, Constant)) + def provides_self_access(self, node, unit): """ @@ -134,22 +170,6 @@ return all_target_names and all_target_names[0] - def get_attribute_and_value(self, obj): - - """ - Return (attribute, value) details for the given 'obj', where an - attribute of None can be returned for constant objects, and where None - can be returned as the result where no concrete details can be provided. - """ - - if isinstance(obj, Constant): - return None, obj - - if isinstance(obj, Attr): - return obj, obj.get_value() - - return None - def possible_attributes_from_annotation(self, node): """ @@ -240,6 +260,17 @@ return targets + def possible_accessors_for_attribute(self, attrname): + + "Return possible accessors given the single 'attrname'." + + targets = set() + + for target_name in self.objtable.any_possible_objects([attrname]): + targets.add(self.objtable.get_object(target_name)) + + return targets + def used_by_unit(node): """ diff -r bdc835dee81d -r 4d49311d3659 micropython/deduce.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/micropython/deduce.py Thu Apr 25 18:08:32 2013 +0200 @@ -0,0 +1,242 @@ +#!/usr/bin/env python + +""" +Perform deductions on an inspected program. + +Copyright (C) 2006, 2007, 2010, 2011, 2012, 2013 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.common import * +from micropython.data import * +from micropython.errors import * +import compiler.ast + +# Source code classes. + +class DeducedSource(ASTVisitor): + + "A module upon which deductions of code behaviour are made." + + def __init__(self, module, program): + self.visitor = self + self.module = module + self.program = program + self.objtable = program.get_object_table() + self.units = [] + + def get_unit(self): + return self.units[-1] + + def get_module(self): + return self.units[0] + + def deduce(self): + + "Process the module, making deductions." + + self.dispatch(self.module.astnode) + + def dispatch(self, node, *args): + + "NOTE: From compiler.visitor.ASTVisitor." + + try: + return node.visit(self.visitor, *args) + except AttributeError: + # NOTE: Obligatory hack to find real attribute errors. + if isinstance(node, (Getattr, AssAttr)): + raise + return self.visitor.default(node, *args) + + def _visitUnit(self, node): + + """ + Track entry into program units in order to support various attribute + access operations. + """ + + if not used_by_unit(node): + return + + self.units.append(node.unit) + self.dispatch(node.node) + self.units.pop() + + visitModule = visitClass = visitFunction = _visitUnit + + def _visitAttr(self, node): + + """ + Perform deductions on attribute accesses, adding annotations to the node + that can be used by subsequent activities. + """ + + unit = self.get_unit() + + # The target, on which the access is performed, may influence the effect + # on the context. We can only reliably assume that a literal constant is + # an instance: all other "instances" may actually be classes in certain + # cases. + + target = node._expr + instance_target = isinstance(target, Const) + + # Attempt to deduce attributes from explicit annotations. + + node._attrs_deduced = attrs = self.possible_attributes_from_annotation(node) + + if len(attrs) == 1: + for attr, value in attrs: + + # Constant values can be obtained directly. + + if self.provides_constant_result(value): + node._access_type = "constant" + node._value_deduced = value + return + + # Static attributes can be obtained via their parent. + + if attr.is_static_attribute(): + node._access_type = "static" + node._attr_deduced = attr + node._set_context = instance_target and "set" or None + return + + # Attributes of self, which is by definition an instance. + + if self.provides_self_access(node, unit): + + # Find instance attributes. + + attr = unit.parent.instance_attributes().get(node.attrname) + + if attr: + node._access_type = "instance" + node._attr_deduced = attr + return + + # Find class attributes. + # The context will be overridden for compatible class attributes + # only. + + attr = unit.parent.get(node.attrname) + + if attr: + + # Constant attributes. + + if attr.is_strict_constant(): + if self.provides_constant_result(attr.get_value()): + node._access_type = "constant" + node._value_deduced = attr.get_value() + return + + # Compatible class attributes. + + if attr.defined_within_hierarchy(): + node._access_type = "static" + node._attr_deduced = attr + node._set_context = "set" + return + + # Incompatible class attributes. + + elif attr.defined_outside_hierarchy(): + node._access_type = "static" + node._attr_deduced = attr + return + + # Unknown or mixed compatibility. + + node._access_type = "static" + node._attr_deduced = attr + node._set_context = "cond" + return + + # Usage observations, both specific to this node's region of the program + # and also applicable to the lifespan of the affected name. + + specific_targets = self.possible_accessors_from_usage(node, defining_users=0) + targets = self.possible_accessors_from_usage(node, defining_users=1) + + # Record whether types were already deduced. If not, get types using + # only this attribute. + + if not specific_targets or not targets: + attribute_targets = self.possible_accessors_for_attribute(node.attrname) + if not specific_targets: + specific_targets = attribute_targets + if not targets: + targets = attribute_targets + + node._attrs_deduced_from_specific_usage = self.get_attributes(specific_targets, node.attrname) + node._attrs_deduced_from_usage = attrs = self.get_attributes(targets, node.attrname) + + # Generate optimisations where only a single attribute applies. + + if attrs and len(attrs) == 1: + for attr in attrs: + + # Static attributes, but potentially non-static targets. + + if attr.is_static_attribute(): + + # Static attributes may be accompanied by a different context + # depending on the accessor. + # NOTE: Should determine whether the context is always replaced. + + node._access_type = "static" + node._attr_deduced = attr + node._set_context = instance_target and "set" or "cond" + return + + # Non-static attributes. + + node._access_type = "instance" + node._attr_deduced = attr + return + + # Test for compatible attribute positioning. + + elif attrs: + positions = set([(attr.is_static_attribute(), attr.position) for attr in attrs]) + + # Permit a position-based access only on non-static attributes since + # access to static attributes may happen via instances and thus not + # be relative to the accessor but to its parent. + + if len(positions) == 1: + for position in positions: + if not position[0]: + node._access_type = "positioned" + node._position_deduced = position[0] + return + + # With no usable deductions, generate a table-based access. + + node._access_type = "unknown" + node._set_context = "cond" + + visitAssAttr = visitGetattr = _visitAttr + +# Convenience functions. + +def deduce(program): + for module in program.get_importer().get_modules(): + DeducedSource(module, program).deduce() + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r bdc835dee81d -r 4d49311d3659 micropython/syspython.py --- a/micropython/syspython.py Sat Apr 20 00:59:58 2013 +0200 +++ b/micropython/syspython.py Thu Apr 25 18:08:32 2013 +0200 @@ -43,6 +43,15 @@ def quoted_name(s): return compiler.ast.Const(s) +# Special function names. +# NOTE: Some of the assignment operations should not be supported unless +# NOTE: attribute usage observations are being made. + +assattr_functions = ("__storeattrcontext__", "__storeattrcontext__", "__storeattr__", + "__storeattrindex__", None) +getattr_functions = ("__loadattrcontext__", "__loadattrcontextcond__", "__loadattr__", + "__loadattrindex__", "__loadattrindexcontextcond__") + # Source code classes. class ConvertedSource(ASTVisitor): @@ -475,6 +484,96 @@ return None + def _visitAttr(self, node, expr=None): + unit = self.get_unit() + + # Choose the appropriate special functions. + + (opattrcontext, opattrcontextcond, opattr, + opattrindex, opattrindexcontextcond) = expr and assattr_functions or getattr_functions + + accessor = self.dispatch(node.expr) + + # Generate already-deduced accesses. + + if node._access_type == "constant": + return self._generateValue(node._value_deduced) + + # Generate accesses via static objects and instances. + + if node._attr_deduced: + if node._set_context == "set": + op = opattrcontext + elif node._set_context == "cond": + op = opattrcontextcond + else: + op = opattr + + # Handle unsupported operations. + + if not op: + raise TranslateError("Storing of class attribute %r via self not permitted." % node.attrname) + + # Define the arguments: accessor, attribute name and optional value. + + args = [ + node._access_type == "static" and \ + self._generateValue(node._attr_deduced.parent) or accessor, + special_name(node.attrname) + ] + + if expr: + args.append(expr) + + return compiler.ast.CallFunc(special_name(op), args) + + # Positioned accesses are normal accesses via instances. + + if node._access_type == "positioned": + args = [accessor, special_name(node.attrname)] + if expr: + args.append(expr) + return compiler.ast.CallFunc(special_name(opattr), args) + + # With no usable deductions, generate a table-based access. + + args = [accessor, special_name(node.attrname)] + if expr: + args.append(expr) + access = compiler.ast.CallFunc(special_name(opattrindexcontextcond), args) + + # class.__class__ => __builtins__.type + + if node.attrname == "__class__": + + # __storetemp__(n, ) + # __isclass__(n) and __loadattr__(__builtins__, type) or + + temp = quoted_name(unit.temp_usage) + unit.temp_usage += 1 + + return compiler.ast.Stmt([ + compiler.ast.CallFunc(special_name("__storetemp__"), [temp, access]), + compiler.ast.Or([ + compiler.ast.And([ + compiler.ast.CallFunc( + special_name("__isclass__"), + [compiler.ast.CallFunc(special_name("__loadtemp__"), [temp])] + ), + compiler.ast.CallFunc( + special_name("__loadattr__"), + [special_name("__builtins__"), special_name("type")] + ) + ]), + access + ]) + ]) + + # General accesses. + + else: + return access + # Expressions. def visitAdd(self, node): @@ -484,63 +583,7 @@ return compiler.ast.And([self.dispatch(n) for n in node.nodes]) def visitAssAttr(self, node, expr): - - # NOTE: Derived from Getattr support. - - accessor = self.dispatch(node.expr) - - # NOTE: Replicate the _generateAttr logic. - # NOTE: Should be able to store concrete value details on generated - # NOTE: nodes, such as whether an expression yields a constant. - - # NOTE: Known targets: - # NOTE: __storeattr__ and __storeattrcontext__ - - # NOTE: Attributes of self. - - # Usage observations. - - targets = self.possible_accessors_from_usage(node, defining_users=0) - - # Record whether types were already deduced. If not, get types using - # only this attribute. - - if not targets: - targets = self.possible_accessors_for_attribute(node.attrname) - - attrs = self.get_attributes(targets, node.attrname) - - # Generate optimisations where only a single attribute applies. - - if len(attrs) == 1: - attr = attrs[0] - - # Static attributes. - - if attr.is_static_attribute(): - - # Static attributes may be accompanied by a different context - # depending on the accessor. - # NOTE: Should determine whether the context is always replaced. - - return compiler.ast.CallFunc( - special_name("__storeattrcontextcond__"), - [accessor, special_name(node.attrname), expr] - ) - - # Non-static attributes. - - return compiler.ast.CallFunc( - special_name("__storeattr__"), - [accessor, special_name(node.attrname), expr] - ) - - # With no usable deductions, generate a table-based access. - - return compiler.ast.CallFunc( - special_name("__storeattrindex__"), - [accessor, special_name(node.attrname), expr] - ) + return self._visitAttr(node, expr) def visitAssList(self, node, expr): return compiler.ast.Stmt([ @@ -660,169 +703,7 @@ return self._visitBinary(node) def visitGetattr(self, node, expr=None): - if expr: - return self.visitAssAttr(node, expr) - - unit = self.get_unit() - - accessor = self.dispatch(node.expr) - - # The target, on which the access is performed, may influence the effect - # on the context. We can only reliably assume that a literal constant is - # an instance: all other "instances" may actually be classes in certain - # cases. - - target = node._expr - instance_target = isinstance(target, Const) - - # Attempt to deduce attributes from explicit annotations. - - attrs = self.possible_attributes_from_annotation(node) - - if len(attrs) == 1: - attr, value = attrs[0] - - # Constant values can be obtained directly. - - v = self._generateValue(value) - if v: return v - - # Static attributes can be obtained via their parent. - - if attr.is_static_attribute(): - return compiler.ast.CallFunc( - special_name(instance_target and "__loadattrcontext__" or "__loadattr__"), - [self._generateValue(attr.parent), special_name(node.attrname)]) - - # Attributes of self, which is by definition an instance. - - if self.provides_self_access(node, unit): - - # Find instance attributes. - - attr = unit.parent.instance_attributes().get(node.attrname) - - if attr: - - # Emit self.attrname without context overriding. - - return compiler.ast.CallFunc( - special_name("__loadattr__"), [ - accessor, special_name(node.attrname) - ]) - - # Find class attributes. - # The context will be overridden for compatible class attributes - # only. - - attr = unit.parent.get(node.attrname) - - if attr: - - # Constant attributes. - - if attr.is_strict_constant(): - v = self._generateValue(attr.get_value()) - if v: return v - - # Compatible class attributes. - - if attr.defined_within_hierarchy(): - return compiler.ast.CallFunc( - special_name("__loadattrcontext__"), [ - self._generateValue(attr.parent), special_name(node.attrname) - ]) - - # Incompatible class attributes. - - elif attr.defined_outside_hierarchy(): - return compiler.ast.CallFunc( - special_name("__loadattr__"), [ - self._generateValue(attr.parent), special_name(node.attrname) - ]) - - # Unknown or mixed compatibility. - - return compiler.ast.CallFunc( - special_name("__loadattrcontextcond__"), [ - self._generateValue(attr.parent), special_name(node.attrname) - ]) - - # Usage observations. - - targets = self.possible_accessors_from_usage(node, defining_users=0) - - # Record whether types were already deduced. If not, get types using - # only this attribute. - - if not targets: - targets = self.possible_accessors_for_attribute(node.attrname) - - attrs = self.get_attributes(targets, node.attrname) - - # Generate optimisations where only a single attribute applies. - - if len(attrs) == 1: - attr = attrs[0] - - # Static attributes, but potentially non-static targets. - - if attr.is_static_attribute(): - - # Static attributes may be accompanied by a different context - # depending on the accessor. - # NOTE: Should determine whether the context is always replaced. - - return compiler.ast.CallFunc( - special_name(instance_target and "__loadattrcontext__" or "__loadattrcontextcond__"), - [accessor, special_name(node.attrname)] - ) - - # Non-static attributes. - - return compiler.ast.CallFunc( - special_name("__loadattr__"), - [accessor, special_name(node.attrname)] - ) - - # With no usable deductions, generate a table-based access. - - access = compiler.ast.CallFunc( - special_name("__loadattrindexcontextcond__"), - [accessor, special_name(node.attrname)] - ) - - # class.__class__ => __builtins__.type - - if node.attrname == "__class__": - - # __storetemp__(n, ) - # __isclass__(n) and __loadattr__(__builtins__, type) or - - temp = quoted_name(unit.temp_usage) - unit.temp_usage += 1 - - return compiler.ast.Stmt([ - compiler.ast.CallFunc(special_name("__storetemp__"), [temp, access]), - compiler.ast.Or([ - compiler.ast.And([ - compiler.ast.CallFunc( - special_name("__isclass__"), - [compiler.ast.CallFunc(special_name("__loadtemp__"), [temp])] - ), - compiler.ast.CallFunc( - special_name("__loadattr__"), - [special_name("__builtins__"), special_name("type")] - ) - ]), - access - ]) - ]) - - # General accesses. - - else: - return access + return self._visitAttr(node, expr) def visitGenExpr(self, node): return compiler.ast.GenExpr(self.dispatch(node.code)) @@ -982,33 +863,6 @@ def visitUnarySub(self, node): return self._visitUnary(node) - # Type-related methods. - - def possible_accessor_types(self, node, defining_users=1): - return set([tn for (tn, st) in ASTVisitor.possible_accessor_types(self, node, defining_users)]) - - def get_possible_accessors(self, attrname): - - "Return a list of accessors supporting 'attrname'." - - targets = [] - - for target_name in self.objtable.any_possible_objects([attrname]): - targets.append(self.objtable.get_object(target_name)) - - return targets - - def get_attributes(self, targets, attrname): - - "Return a list of attributes for 'targets' supporting 'attrname'." - - attributes = [] - - for target in targets: - attributes.append(self.objtable.access(target.full_name(), attrname)) - - return attributes - # Convenience functions. def convert(module, program, filename): diff -r bdc835dee81d -r 4d49311d3659 test.py --- a/test.py Sat Apr 20 00:59:58 2013 +0200 +++ b/test.py Thu Apr 25 18:08:32 2013 +0200 @@ -1,8 +1,10 @@ #!/usr/bin/env python +from micropython.graph import get_graph import micropython.cmd +import micropython.deduce import micropython.report -from micropython.graph import get_graph +import micropython.syspython import rsvp import sys import os @@ -83,6 +85,10 @@ b = i.get_module("__builtins__") + # Perform deductions. + + micropython.deduce.deduce(p) + # Make a report. if "-d" in args: @@ -94,6 +100,17 @@ print "Generating report in", directory micropython.report.report(p, directory) + # Make the syspython representation. + + if "-s" in args: + try: + directory = args[args.index("-s") + 1] + except IndexError: + print "No directory specified. Not generating syspython program." + else: + print "Generating syspython program in", directory + micropython.syspython.translate(p, directory) + if "-G" in args: try: graph = args[args.index("-G") + 1] diff -r bdc835dee81d -r 4d49311d3659 tests/attributes_class_inherited_static.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/attributes_class_inherited_static.py Thu Apr 25 18:08:32 2013 +0200 @@ -0,0 +1,12 @@ +#!/usr/bin/env python + +class C: + x = 1 + +class D(C): + pass + +result1_1 = C.x +result2_1 = D.x + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r bdc835dee81d -r 4d49311d3659 tests/attributes_class_inherited_static_multiple_values.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/attributes_class_inherited_static_multiple_values.py Thu Apr 25 18:08:32 2013 +0200 @@ -0,0 +1,13 @@ +#!/usr/bin/env python + +class C: + x = 1 + x = 2 + +class D(C): + pass + +result_1 = C.x +result_2 = D.x + +# vim: tabstop=4 expandtab shiftwidth=4