From ba9876c992c5657b18c4ba93eed8ac3dd347751f Mon Sep 17 00:00:00 2001 From: Luke Kenneth Casson Leighton Date: Thu, 1 Jun 2023 18:42:38 +0100 Subject: [PATCH] add pyomo StreamBasedExpressionVisitor https://pyomo.readthedocs.io/en/stable/_modules/pyomo/core/expr/visitor.html part of testing https://bugs.libre-soc.org/show_bug.cgi?id=1094 --- src/openpower/numeric_types.py | 99 ++++ src/openpower/test_visitor.py | 933 +++++++++++++++++++++++++++++++++ src/openpower/visitor.py | 657 +++++++++++++++++++++++ 3 files changed, 1689 insertions(+) create mode 100644 src/openpower/numeric_types.py create mode 100644 src/openpower/test_visitor.py create mode 100644 src/openpower/visitor.py diff --git a/src/openpower/numeric_types.py b/src/openpower/numeric_types.py new file mode 100644 index 00000000..1b4f3015 --- /dev/null +++ b/src/openpower/numeric_types.py @@ -0,0 +1,99 @@ +# ___________________________________________________________________________ +# +# Pyomo: Python Optimization Modeling Objects +# Copyright (c) 2008-2022 +# National Technology and Engineering Solutions of Sandia, LLC +# Under the terms of Contract DE-NA0003525 with National Technology and +# Engineering Solutions of Sandia, LLC, the U.S. Government retains certain +# rights in this software. +# This software is distributed under the 3-clause BSD License. +# ___________________________________________________________________________ + +#: Python set used to identify numeric constants, boolean values, strings +#: and instances of +#: :class:`NonNumericValue `, +#: which is commonly used in code that walks Pyomo expression trees. +#: +#: :data:`nonpyomo_leaf_types` = +#: :data:`native_types ` + +#: { :data:`NonNumericValue ` } +nonpyomo_leaf_types = set() + +# It is *significantly* faster to build the list of types we want to +# test against as a "static" set, and not to regenerate it locally for +# every call. Plus, this allows us to dynamically augment the set +# with new "native" types (e.g., from NumPy) +# +# Note: These type sets are used in set_types.py for domain validation +# For backward compatibility reasons, we include str in the set +# of valid types for bool. We also avoid updating the numeric +# and integer type sets when a new boolean type is registered +# because not all boolean types exhibit numeric properties +# (e.g., numpy.bool_) +# + +#: Python set used to identify numeric constants. This set includes +#: native Python types as well as numeric types from Python packages +#: like numpy, which may be registered by users. +native_numeric_types = {int, float, complex} +native_integer_types = {int} +native_logical_types = {bool} + +_native_boolean_types = {int, bool, str, bytes} + + +#: Python set used to identify numeric constants and related native +#: types. This set includes +#: native Python types as well as numeric types from Python packages +#: like numpy. +#: +#: :data:`native_types` = +#: :data:`native_numeric_types` +#: + { str } +native_types = set([bool, str, type(None), slice, bytes]) +native_types.update(native_numeric_types) +native_types.update(native_integer_types) +native_types.update(_native_boolean_types) +native_types.update(native_logical_types) + +nonpyomo_leaf_types.update(native_types) + + +def RegisterNumericType(new_type): + """ + A utility function for updating the set of types that are + recognized to handle numeric values. + + The argument should be a class (e.g, numpy.float64). + """ + native_numeric_types.add(new_type) + native_types.add(new_type) + nonpyomo_leaf_types.add(new_type) + + +def RegisterIntegerType(new_type): + """ + A utility function for updating the set of types that are + recognized to handle integer values. This also registers the type + as numeric but does not register it as boolean. + + The argument should be a class (e.g., numpy.int64). + """ + native_numeric_types.add(new_type) + native_integer_types.add(new_type) + native_types.add(new_type) + nonpyomo_leaf_types.add(new_type) + + +def RegisterLogicalType(new_type): + """ + A utility function for updating the set of types that are + recognized as handling boolean values. This function does not + register the type of integer or numeric. + + The argument should be a class (e.g., numpy.bool_). + """ + _native_boolean_types.add(new_type) + native_logical_types.add(new_type) + native_types.add(new_type) + nonpyomo_leaf_types.add(new_type) diff --git a/src/openpower/test_visitor.py b/src/openpower/test_visitor.py new file mode 100644 index 00000000..3bc11c7d --- /dev/null +++ b/src/openpower/test_visitor.py @@ -0,0 +1,933 @@ +# ___________________________________________________________________________ +# +# Pyomo: Python Optimization Modeling Objects +# Copyright (c) 2008-2022 +# National Technology and Engineering Solutions of Sandia, LLC +# Under the terms of Contract DE-NA0003525 with National Technology and +# Engineering Solutions of Sandia, LLC, the U.S. Government retains certain +# rights in this software. +# This software is distributed under the 3-clause BSD License. +# ___________________________________________________________________________ +# +# Unit Tests for expression generation +# + +import os +import platform +import sys + +import unittest + +from openpower.logging_intercept import LoggingIntercept +from openpower.numeric_types import native_types, nonpyomo_leaf_types +from openpower.visitor import ( + StreamBasedExpressionVisitor, + RECURSION_LIMIT, + get_stack_depth, +) +#from pyomo.common.log import LoggingIntercept +from io import StringIO + +def sizeof_expression(e): + return len(e.flatten()) + + +class BaseExpression: + def __init__(self, name, exprs): + self.exprs = [name] + list(exprs) + self.name = name + self.args = list(exprs) + + def is_expression_type(self): + return True + + def flatten(self): + res = [] + for x in self.exprs: + if hasattr(x, "exprs"): + res.append(x.exprs) + else: + res.append(x) + return res + + def __str__(self): + return ', '.join(map(str, self.flatten())) + + def __len__(self): return len(self.args) + def __getitem__(self, i): print (self, i); return self.args.__getitem__(i) + +class Expression(BaseExpression): + def __init__(self, I, rule): + super().__init__("expr", [I] + [rule]) + +class SumExpression(BaseExpression): + def __init__(self, exprs): + super().__init__("sum", exprs) + +class ProductExpression(BaseExpression): + def __init__(self, exprs): + super().__init__("prod", exprs) + +class PowExpression(BaseExpression): + def __init__(self, exprs): + super().__init__("pow", exprs) + +class ConcreteModel: + name = "ConcreteModel" + def is_expression_type(self): + return False + +class Var: + def __init__(self, name): + self.name = name + def is_expression_type(self): + return False + def __repr__(self): + return self.name + +class Set(BaseExpression): + def __init__(self, initialize=None): + super().__init__("set", initialize) + def is_expression_type(self): + return False + + +class BaseStreamBasedVisitorTests(object): + def setUp(self): + self.m = m = ConcreteModel() + self.maxDiff = 5000 + m.x = Var("x") + m.y = Var("y") + m.z = Var("z") + # Note: we do not use the operator overloading to generate the + # expression so that the structure is constant even when we make + # adjustments to the expression generators + self.e = SumExpression( + [ + PowExpression((m.x, 2)), + m.y, + ProductExpression((m.z, SumExpression([m.x, m.y]))), + ] + ) + + def test_bad_args(self): + with self.assertRaisesRegex( + RuntimeError, "Unrecognized keyword arguments: {'foo': None}" + ): + StreamBasedExpressionVisitor(foo=None) + + def test_default(self): + walker = StreamBasedExpressionVisitor() + ans = self.walk(walker, self.e) + ref = [[[], []], [], [[], [[], []]]] + self.assertEqual(ans, ref) + + def test_beforeChild(self): + def before(node, child, child_idx): + if type(child) in nonpyomo_leaf_types or not child.is_expression_type(): + return False, [child] + + walker = StreamBasedExpressionVisitor(beforeChild=before) + ans = self.walk(walker, self.e) + m = self.m + ref = [[[m.x], [2]], [m.y], [[m.z], [[m.x], [m.y]]]] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, m.x) + ref = [] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, 2) + ref = [] + self.assertEqual(str(ans), str(ref)) + + def test_initializeWalker_beforeChild(self): + def before(node, child, child_idx): + if type(child) in nonpyomo_leaf_types or not child.is_expression_type(): + return False, child + + def initialize(expr): + ans = before(None, expr, 0) + if ans is None: + return True, expr + else: + return ans + + walker = StreamBasedExpressionVisitor( + beforeChild=before, initializeWalker=initialize + ) + ans = self.walk(walker, self.e) + m = self.m + ref = [[m.x, 2], m.y, [m.z, [m.x, m.y]]] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, m.x) + ref = m.x + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, 2) + ref = 2 + self.assertEqual(str(ans), str(ref)) + + def test_beforeChild_exitNode(self): + def before(node, child, child_idx): + if type(child) in nonpyomo_leaf_types or not child.is_expression_type(): + return False, [child] + + def exit(node, data): + if hasattr(node, 'getname'): + data.insert(0, node.getname()) + else: + data.insert(0, str(node)) + return data + + walker = StreamBasedExpressionVisitor(beforeChild=before, exitNode=exit) + ans = self.walk(walker, self.e) + m = self.m + ref = [ + 'sum', + ['pow', [m.x], [2]], + [m.y], + ['prod', [m.z], ['sum', [m.x], [m.y]]], + ] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, m.x) + ref = ['x'] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, 2) + ref = ['2'] + self.assertEqual(str(ans), str(ref)) + + def test_beforeChild_enterNode_exitNode(self): + i = [0] + + def before(node, child, child_idx): + if type(child) in nonpyomo_leaf_types or not child.is_expression_type(): + return False, [child] + + def enter(node): + i[0] += 1 + return None, [i[0]] + + def exit(node, data): + if hasattr(node, 'getname'): + data.insert(0, node.getname()) + else: + data.insert(0, str(node)) + return data + + walker = StreamBasedExpressionVisitor( + beforeChild=before, enterNode=enter, exitNode=exit + ) + ans = self.walk(walker, self.e) + m = self.m + ref = [ + 'sum', + 1, + ['pow', 2, [m.x], [2]], + [m.y], + ['prod', 3, [m.z], ['sum', 4, [m.x], [m.y]]], + ] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, m.x) + ref = ['x', 5] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, 2) + ref = ['2', 6] + self.assertEqual(str(ans), str(ref)) + + def test_old_beforeChild(self): + def before(node, child): + if type(child) in nonpyomo_leaf_types or not child.is_expression_type(): + return False, [child] + + os = StringIO() + with LoggingIntercept(os, 'pyomo'): + walker = StreamBasedExpressionVisitor(beforeChild=before) + #output = os.getvalue() + #self.assertIn( + # "Note that the API for the StreamBasedExpressionVisitor " + # "has changed to include the child index for the beforeChild() " + # "method", + # output.replace('\n', ' '), + #) + + ans = self.walk(walker, self.e) + m = self.m + ref = [[[m.x], [2]], [m.y], [[m.z], [[m.x], [m.y]]]] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, m.x) + ref = [] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, 2) + ref = [] + self.assertEqual(str(ans), str(ref)) + + def test_reduce_in_accept(self): + def enter(node): + return None, 1 + + def accept(node, data, child_result, child_idx): + return data + child_result + + walker = StreamBasedExpressionVisitor(enterNode=enter, acceptChildResult=accept) + # 4 operators, 6 leaf nodes + self.assertEqual(self.walk(walker, self.e), 10) + + def test_sizeof_expression(self): + self.assertEqual(sizeof_expression(self.e), 10) + + def test_enterNode(self): + # This is an alternative way to implement the beforeChild test: + def enter(node): + if type(node) in nonpyomo_leaf_types or not node.is_expression_type(): + return (), [node] + return node.args, [] + + walker = StreamBasedExpressionVisitor(enterNode=enter) + m = self.m + + ans = self.walk(walker, self.e) + ref = [[[m.x], [2]], [m.y], [[m.z], [[m.x], [m.y]]]] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, m.x) + ref = [m.x] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, 2) + ref = [2] + self.assertEqual(str(ans), str(ref)) + + def test_enterNode_noLeafList(self): + # This is an alternative way to implement the beforeChild test: + def enter(node): + if type(node) in nonpyomo_leaf_types or not node.is_expression_type(): + return (), node + return node.args, [] + + walker = StreamBasedExpressionVisitor(enterNode=enter) + m = self.m + + ans = self.walk(walker, self.e) + ref = [[m.x, 2], m.y, [m.z, [m.x, m.y]]] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, m.x) + ref = m.x + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, 2) + ref = 2 + self.assertEqual(str(ans), str(ref)) + + def test_enterNode_withFinalize(self): + # This is an alternative way to implement the beforeChild test: + def enter(node): + if type(node) in nonpyomo_leaf_types or not node.is_expression_type(): + return (), node + return node.args, [] + + def finalize(result): + if type(result) is list: + return result + else: + return [result] + + walker = StreamBasedExpressionVisitor(enterNode=enter, finalizeResult=finalize) + m = self.m + + ans = self.walk(walker, self.e) + ref = [[m.x, 2], m.y, [m.z, [m.x, m.y]]] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, m.x) + ref = [m.x] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, 2) + ref = [2] + self.assertEqual(str(ans), str(ref)) + + def test_exitNode(self): + # This is an alternative way to implement the beforeChild test: + def exit(node, data): + if data: + return data + else: + return [node] + + walker = StreamBasedExpressionVisitor(exitNode=exit) + m = self.m + + ans = self.walk(walker, self.e) + ref = [[[m.x], [2]], [m.y], [[m.z], [[m.x], [m.y]]]] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, m.x) + ref = [m.x] + self.assertEqual(str(ans), str(ref)) + + ans = self.walk(walker, 2) + ref = [2] + self.assertEqual(str(ans), str(ref)) + + def test_beforeChild_acceptChildResult_afterChild(self): + counts = [0, 0, 0] + + def before(node, child, child_idx): + counts[0] += 1 + if type(child) in nonpyomo_leaf_types or not child.is_expression_type(): + return False, None + + def accept(node, data, child_result, child_idx): + counts[1] += 1 + + def after(node, child, child_idx): + counts[2] += 1 + + walker = StreamBasedExpressionVisitor( + beforeChild=before, acceptChildResult=accept, afterChild=after + ) + ans = self.walk(walker, self.e) + m = self.m + self.assertEqual(ans, None) + self.assertEqual(counts, [9, 9, 9]) + + def test_OLD_beforeChild_acceptChildResult_afterChild(self): + counts = [0, 0, 0] + + def before(node, child): + counts[0] += 1 + if type(child) in nonpyomo_leaf_types or not child.is_expression_type(): + return False, None + + def accept(node, data, child_result): + counts[1] += 1 + + def after(node, child): + counts[2] += 1 + + os = StringIO() + with LoggingIntercept(os, 'pyomo'): + walker = StreamBasedExpressionVisitor( + beforeChild=before, acceptChildResult=accept, afterChild=after + ) + #self.assertIn( + # "Note that the API for the StreamBasedExpressionVisitor " + # "has changed to include the child index for the " + # "beforeChild() method", + # os.getvalue().replace('\n', ' '), + #) + #self.assertIn( + # "Note that the API for the StreamBasedExpressionVisitor " + # "has changed to include the child index for the " + # "acceptChildResult() method", + # os.getvalue().replace('\n', ' '), + #) + #self.assertIn( + # "Note that the API for the StreamBasedExpressionVisitor " + # "has changed to include the child index for the " + # "afterChild() method", + # os.getvalue().replace('\n', ' '), + #) + + ans = self.walk(walker, self.e) + m = self.m + self.assertEqual(ans, None) + self.assertEqual(counts, [9, 9, 9]) + + def test_enterNode_acceptChildResult_beforeChild(self): + ans = [] + + def before(node, child, child_idx): + if type(child) in nonpyomo_leaf_types or not child.is_expression_type(): + return False, child + + def accept(node, data, child_result, child_idx): + if data is not child_result: + data.append(child_result) + return data + + def enter(node): + return node.args, ans + + walker = StreamBasedExpressionVisitor( + enterNode=enter, beforeChild=before, acceptChildResult=accept + ) + ans = self.walk(walker, self.e) + m = self.m + ref = [m.x, 2, m.y, m.z, m.x, m.y] + self.assertEqual(str(ans), str(ref)) + + def test_finalize(self): + ans = [] + + def before(node, child, child_idx): + if type(child) in nonpyomo_leaf_types or not child.is_expression_type(): + return False, child + + def accept(node, data, child_result, child_idx): + if data is not child_result: + data.append(child_result) + return data + + def enter(node): + return node.args, ans + + def finalize(result): + return len(result) + + walker = StreamBasedExpressionVisitor( + enterNode=enter, + beforeChild=before, + acceptChildResult=accept, + finalizeResult=finalize, + ) + ans = self.walk(walker, self.e) + self.assertEqual(ans, 6) + + def test_all_function_pointers(self): + ans = [] + + def name(x): + if type(x) in nonpyomo_leaf_types: + return str(x) + else: + return x.name + + def initialize(expr): + ans.append("Initialize") + return True, None + + def enter(node): + ans.append("Enter %s" % (name(node))) + + def exit(node, data): + ans.append("Exit %s" % (name(node))) + + def before(node, child, child_idx): + ans.append("Before %s (from %s)" % (name(child), name(node))) + + def accept(node, data, child_result, child_idx): + ans.append("Accept into %s" % (name(node))) + + def after(node, child, child_idx): + ans.append("After %s (from %s)" % (name(child), name(node))) + + def finalize(result): + ans.append("Finalize") + + walker = StreamBasedExpressionVisitor( + initializeWalker=initialize, + enterNode=enter, + exitNode=exit, + beforeChild=before, + acceptChildResult=accept, + afterChild=after, + finalizeResult=finalize, + ) + self.assertIsNone(self.walk(walker, self.e)) + self.assertEqual( + "\n".join(ans), + """Initialize +Enter sum +Before pow (from sum) +Enter pow +Before x (from pow) +Enter x +Exit x +Accept into pow +After x (from pow) +Before 2 (from pow) +Enter 2 +Exit 2 +Accept into pow +After 2 (from pow) +Exit pow +Accept into sum +After pow (from sum) +Before y (from sum) +Enter y +Exit y +Accept into sum +After y (from sum) +Before prod (from sum) +Enter prod +Before z (from prod) +Enter z +Exit z +Accept into prod +After z (from prod) +Before sum (from prod) +Enter sum +Before x (from sum) +Enter x +Exit x +Accept into sum +After x (from sum) +Before y (from sum) +Enter y +Exit y +Accept into sum +After y (from sum) +Exit sum +Accept into prod +After sum (from prod) +Exit prod +Accept into sum +After prod (from sum) +Exit sum +Finalize""", + ) + + def test_all_derived_class(self): + def name(x): + if type(x) in nonpyomo_leaf_types: + return str(x) + else: + return x.name + + class all_callbacks(StreamBasedExpressionVisitor): + def __init__(self): + self.ans = [] + super(all_callbacks, self).__init__() + + def initializeWalker(self, expr): + self.ans.append("Initialize") + return True, None + + def enterNode(self, node): + self.ans.append("Enter %s" % (name(node))) + + def exitNode(self, node, data): + self.ans.append("Exit %s" % (name(node))) + + def beforeChild(self, node, child, child_idx): + self.ans.append("Before %s (from %s)" % (name(child), name(node))) + + def acceptChildResult(self, node, data, child_result, child_idx): + self.ans.append("Accept into %s" % (name(node))) + + def afterChild(self, node, child, child_idx): + self.ans.append("After %s (from %s)" % (name(child), name(node))) + + def finalizeResult(self, result): + self.ans.append("Finalize") + + walker = all_callbacks() + self.assertIsNone(self.walk(walker, self.e)) + self.assertEqual( + "\n".join(walker.ans), + """Initialize +Enter sum +Before pow (from sum) +Enter pow +Before x (from pow) +Enter x +Exit x +Accept into pow +After x (from pow) +Before 2 (from pow) +Enter 2 +Exit 2 +Accept into pow +After 2 (from pow) +Exit pow +Accept into sum +After pow (from sum) +Before y (from sum) +Enter y +Exit y +Accept into sum +After y (from sum) +Before prod (from sum) +Enter prod +Before z (from prod) +Enter z +Exit z +Accept into prod +After z (from prod) +Before sum (from prod) +Enter sum +Before x (from sum) +Enter x +Exit x +Accept into sum +After x (from sum) +Before y (from sum) +Enter y +Exit y +Accept into sum +After y (from sum) +Exit sum +Accept into prod +After sum (from prod) +Exit prod +Accept into sum +After prod (from sum) +Exit sum +Finalize""", + ) + + def test_all_derived_class_oldAPI(self): + def name(x): + if type(x) in nonpyomo_leaf_types: + return str(x) + else: + return x.name + + class all_callbacks(StreamBasedExpressionVisitor): + def __init__(self): + self.ans = [] + super(all_callbacks, self).__init__() + + def enterNode(self, node): + self.ans.append("Enter %s" % (name(node))) + + def exitNode(self, node, data): + self.ans.append("Exit %s" % (name(node))) + + def beforeChild(self, node, child): + self.ans.append("Before %s (from %s)" % (name(child), name(node))) + + def acceptChildResult(self, node, data, child_result): + self.ans.append("Accept into %s" % (name(node))) + + def afterChild(self, node, child): + self.ans.append("After %s (from %s)" % (name(child), name(node))) + + def finalizeResult(self, result): + self.ans.append("Finalize") + + os = StringIO() + with LoggingIntercept(os, 'pyomo'): + walker = all_callbacks() + #self.assertIn( + # "Note that the API for the StreamBasedExpressionVisitor " + # "has changed to include the child index for the " + # "beforeChild() method", + # os.getvalue().replace('\n', ' '), + #) + #self.assertIn( + # "Note that the API for the StreamBasedExpressionVisitor " + # "has changed to include the child index for the " + # "acceptChildResult() method", + # os.getvalue().replace('\n', ' '), + #) + #self.assertIn( + # "Note that the API for the StreamBasedExpressionVisitor " + # "has changed to include the child index for the " + # "afterChild() method", + # os.getvalue().replace('\n', ' '), + #) + + self.assertIsNone(self.walk(walker, self.e)) + self.assertEqual( + "\n".join(walker.ans), + """Enter sum +Before pow (from sum) +Enter pow +Before x (from pow) +Enter x +Exit x +Accept into pow +After x (from pow) +Before 2 (from pow) +Enter 2 +Exit 2 +Accept into pow +After 2 (from pow) +Exit pow +Accept into sum +After pow (from sum) +Before y (from sum) +Enter y +Exit y +Accept into sum +After y (from sum) +Before prod (from sum) +Enter prod +Before z (from prod) +Enter z +Exit z +Accept into prod +After z (from prod) +Before sum (from prod) +Enter sum +Before x (from sum) +Enter x +Exit x +Accept into sum +After x (from sum) +Before y (from sum) +Enter y +Exit y +Accept into sum +After y (from sum) +Exit sum +Accept into prod +After sum (from prod) +Exit prod +Accept into sum +After prod (from sum) +Exit sum +Finalize""", + ) + + +class TestStreamBasedExpressionVisitor_Recursive( + BaseStreamBasedVisitorTests, unittest.TestCase +): + def walk(self, walker, expr): + return walker.walk_expression(expr) + + +class TestStreamBasedExpressionVisitor_NonRecursive( + BaseStreamBasedVisitorTests, unittest.TestCase +): + def walk(self, walker, expr): + return walker.walk_expression_nonrecursive(expr) + + +def fill_stack(n, fcn, *args): + if n: + return fill_stack(n - 1, fcn, *args) + else: + return fcn(*args) + + +class TestStreamBasedExpressionVisitor_Deep(unittest.TestCase): + def setUp(self): + self.m = m = ConcreteModel() + m.x = Var("x") + m.I = Set(initialize=range(2 * RECURSION_LIMIT)) + + def _rule(m, i): + if i: + return m.e[i - 1] + else: + return m.x + + m.e = Expression(m.I, rule=_rule) + + def evaluate_bx(self): + def before(node, child, idx): + if type(child) in native_types or not child.is_expression_type(): + return False, value(child) + return True, None + + def exit(node, data): + return data[0] + 1 + + return StreamBasedExpressionVisitor(beforeChild=before, exitNode=exit) + + def evaluate_bex(self): + def before(node, child, idx): + if type(child) in native_types or not child.is_expression_type(): + return False, value(child) + return True, None + + def enter(node): + return None, [] + + def exit(node, data): + return data[0] + 1 + + return StreamBasedExpressionVisitor( + beforeChild=before, enterNode=enter, exitNode=exit + ) + + def evaluate_abex(self): + def before(node, child, idx): + if type(child) in native_types or not child.is_expression_type(): + return False, value(child) + return True, None + + def enter(node): + return None, 0 + + def accept(node, data, child_result, child_idx): + return data + child_result + + def exit(node, data): + return data + 1 + + return StreamBasedExpressionVisitor( + beforeChild=before, acceptChildResult=accept, enterNode=enter, exitNode=exit + ) + + def run_walker(self, walker): + m = self.m + m.x = 10 + self.assertEqual( + 2 * RECURSION_LIMIT + 10, + walker.walk_expression(m.e[2 * RECURSION_LIMIT - 1]), + ) + self.assertEqual( + 2 * RECURSION_LIMIT + 10, + walker.walk_expression_nonrecursive(m.e[2 * RECURSION_LIMIT - 1]), + ) + + # This is a "magic parameter" that quantifies the overhead + # needed by the system to convert the recursive walker to a + # nonrecursive one. + # + # Note: this needs to be 13 if pytest is run as a script, and 14 + # if pytest is run as "python -m". We will use 14, and then add + # 2 (instead of 1) to generate the recursion error. Note that + # the stack handling is different on GHA, and we need to fill an + # additional frame (for a total of 3) to trigger the recursion + # error. + # + TESTING_OVERHEAD = 14 + warn_msg = "Unexpected RecursionError walking an expression tree.\n" + + if platform.python_implementation() == 'PyPy': + # We have not yet determined how to trigger the + # RecursionError on PyPy + cases = [(0, "")] + elif os.environ.get('GITHUB_ACTIONS', '') and sys.platform.startswith('win'): + # The test for handling RecursionError appears to fail + # inexplicably on GHA/Windows under pytest: the + # RecursionError that is supposed to be raised is not + # raised, and instead the system actually dies on stack + # overflow error + cases = [] + else: + # 3 sufficed through Python 3.10, but appeared to need to be + # raised to 5 for recent 3.11 builds (3.11.2) + cases = [(0, ""), (5, warn_msg)] + + head_room = sys.getrecursionlimit() - get_stack_depth() + for n, msg in cases: + with LoggingIntercept() as LOG: + self.assertEqual( + 2 * RECURSION_LIMIT + 10, + fill_stack( + head_room - RECURSION_LIMIT - TESTING_OVERHEAD + n, + walker.walk_expression, + m.e[2 * RECURSION_LIMIT - 1], + ), + ) + self.assertEqual(msg, LOG.getvalue()) + + def test_evaluate_bx(self): + return self.run_walker(self.evaluate_bx()) + + def test_evaluate_bex(self): + return self.run_walker(self.evaluate_bex()) + + def test_evaluate_abex(self): + return self.run_walker(self.evaluate_abex()) + + + +if __name__ == "__main__": + unittest.main() diff --git a/src/openpower/visitor.py b/src/openpower/visitor.py new file mode 100644 index 00000000..7ad025cd --- /dev/null +++ b/src/openpower/visitor.py @@ -0,0 +1,657 @@ +# ___________________________________________________________________________ +# +# Pyomo: Python Optimization Modeling Objects +# Copyright (c) 2008-2022 +# National Technology and Engineering Solutions of Sandia, LLC +# Under the terms of Contract DE-NA0003525 with National Technology and +# Engineering Solutions of Sandia, LLC, the U.S. Government retains certain +# rights in this software. +# This software is distributed under the 3-clause BSD License. +# ___________________________________________________________________________ + +from __future__ import division + +import inspect +import logging +import sys +from copy import deepcopy +from collections import deque + +logger = logging.getLogger('pyomo.core') + +from openpower.numeric_types import nonpyomo_leaf_types + + +try: + # sys._getframe is slightly faster than inspect's currentframe, but + # is not guaranteed to exist everywhere + currentframe = sys._getframe +except AttributeError: + currentframe = inspect.currentframe + + +def get_stack_depth(): + n = -1 # skip *this* frame in the count + f = currentframe() + while f is not None: + n += 1 + f = f.f_back + return n + + +# For efficiency, we want to run recursively, but don't want to hit +# Python's recursion limit (because that would be difficult to recover +# from cleanly). However, there is a non-trivial cost to determine the +# current stack depth - and we don't want to hit that for every call. +# Instead, we will assume that the walker is always called with at +# least RECURSION_LIMIT frames available on the stack. When we hit the +# end of that limit, we will actually check how much space is left on +# the stack and run recursively until only 2*RECURSION_LIMIT frames are +# left. For the vast majority of well-formed expressions this approach +# avoids a somewhat costly call to get_stack_depth, but still catches +# the vast majority of cases that could generate a recursion error. +RECURSION_LIMIT = 50 + + +class RevertToNonrecursive(Exception): + pass + + +# NOTE: This module also has dependencies on numeric_expr; however, to +# avoid circular dependencies, we will NOT import them here. Instead, +# until we can resolve the circular dependencies, they will be injected +# into this module by the .current module (which must be imported +# *after* numeric_expr, logocal_expr, and this module. + + +# ------------------------------------------------------- +# +# Visitor Logic +# +# ------------------------------------------------------- + + +class StreamBasedExpressionVisitor(object): + """This class implements a generic stream-based expression walker. + + This visitor walks an expression tree using a depth-first strategy + and generates a full event stream similar to other tree visitors + (e.g., the expat XML parser). The following events are triggered + through callback functions as the traversal enters and leaves nodes + in the tree: + + initializeWalker(expr) -> walk, result + enterNode(N1) -> args, data + {for N2 in args:} + beforeChild(N1, N2) -> descend, child_result + enterNode(N2) -> N2_args, N2_data + [...] + exitNode(N2, n2_data) -> child_result + acceptChildResult(N1, data, child_result) -> data + afterChild(N1, N2) -> None + exitNode(N1, data) -> N1_result + finalizeWalker(result) -> result + + Individual event callbacks match the following signatures: + + walk, result = initializeWalker(self, expr): + + initializeWalker() is called to set the walker up and perform + any preliminary processing on the root node. The method returns + a flag indicating if the tree should be walked and a result. If + `walk` is True, then result is ignored. If `walk` is False, + then `result` is returned as the final result from the walker, + bypassing all other callbacks (including finalizeResult). + + args, data = enterNode(self, node): + + enterNode() is called when the walker first enters a node (from + above), and is passed the node being entered. It is expected to + return a tuple of child `args` (as either a tuple or list) and a + user-specified data structure for collecting results. If None + is returned for args, the node's args attribute is used for + expression types and the empty tuple for leaf nodes. Returning + None is equivalent to returning (None,None). If the callback is + not defined, the default behavior is equivalent to returning + (None, []). + + node_result = exitNode(self, node, data): + + exitNode() is called after the node is completely processed (as + the walker returns up the tree to the parent node). It is + passed the node and the results data structure (defined by + enterNode() and possibly further modified by + acceptChildResult()), and is expected to return the "result" for + this node. If not specified, the default action is to return + the data object from enterNode(). + + descend, child_result = beforeChild(self, node, child, child_idx): + + beforeChild() is called by a node for every child before + entering the child node. The node, child node, and child index + (position in the args list from enterNode()) are passed as + arguments. beforeChild should return a tuple (descend, + child_result). If descend is False, the child node will not be + entered and the value returned to child_result will be passed to + the node's acceptChildResult callback. Returning None is + equivalent to (True, None). The default behavior if not + specified is equivalent to (True, None). + + data = acceptChildResult(self, node, data, child_result, child_idx): + + acceptChildResult() is called for each child result being + returned to a node. This callback is responsible for recording + the result for later processing or passing up the tree. It is + passed the node, result data structure (see enterNode()), child + result, and the child index (position in args from enterNode()). + The data structure (possibly modified or replaced) must be + returned. If acceptChildResult is not specified, it does + nothing if data is None, otherwise it calls data.append(result). + + afterChild(self, node, child, child_idx): + + afterChild() is called by a node for every child node + immediately after processing the node is complete before control + moves to the next child or up to the parent node. The node, + child node, an child index (position in args from enterNode()) + are passed, and nothing is returned. If afterChild is not + specified, no action takes place. + + finalizeResult(self, result): + + finalizeResult() is called once after the entire expression tree + has been walked. It is passed the result returned by the root + node exitNode() callback. If finalizeResult is not specified, + the walker returns the result obtained from the exitNode + callback on the root node. + + Clients interact with this class by either deriving from it and + implementing the necessary callbacks (see above), assigning callable + functions to an instance of this class, or passing the callback + functions as arguments to this class' constructor. + + """ + + # The list of event methods that can either be implemented by + # derived classes or specified as callback functions to the class + # constructor. + # + # This is a dict mapping the callback name to a single character + # that we can use to classify the set of callbacks used by a + # particular Visitor (we define special-purpose node processors for + # certain common combinations). For example, a 'bex' visitor is one + # that supports beforeChild, enterNode, and exitNode, but NOT + # afterChild or acceptChildResult. + client_methods = { + 'enterNode': 'e', + 'exitNode': 'x', + 'beforeChild': 'b', + 'afterChild': 'a', + 'acceptChildResult': 'c', + 'initializeWalker': '', + 'finalizeResult': '', + } + + def __init__(self, **kwds): + # This is slightly tricky: We want derived classes to be able to + # override the "None" defaults here, and for keyword arguments + # to override both. The hasattr check prevents the "None" + # defaults from overriding attributes or methods defined on + # derived classes. + for field in self.client_methods: + if field in kwds: + setattr(self, field, kwds.pop(field)) + elif not hasattr(self, field): + setattr(self, field, None) + if kwds: + raise RuntimeError("Unrecognized keyword arguments: %s" % (kwds,)) + + # Handle deprecated APIs + _fcns = (('beforeChild', 2), ('acceptChildResult', 3), ('afterChild', 2)) + for name, nargs in _fcns: + fcn = getattr(self, name) + if fcn is None: + continue + _args = inspect.getfullargspec(fcn) + _self_arg = 1 if inspect.ismethod(fcn) else 0 + if len(_args.args) == nargs + _self_arg and _args.varargs is None: + print( + "Note that the API for the StreamBasedExpressionVisitor " \ + "has changed to include the child index for the %s() " \ + "method" % (name,))#, file=sys.stderr) + + def wrap(fcn, nargs): + def wrapper(*args): + return fcn(*args[:nargs]) + + return wrapper + + setattr(self, name, wrap(fcn, nargs)) + + self.recursion_stack = None + + # Set up the custom recursive node handler function (customized + # for the specific set of callbacks that are defined for this + # class instance). + recursive_node_handler = '_process_node_' + ''.join( + sorted( + '' if getattr(self, f[0]) is None else f[1] + for f in self.client_methods.items() + ) + ) + self._process_node = getattr( + self, recursive_node_handler, self._process_node_general + ) + + def walk_expression(self, expr): + """Walk an expression, calling registered callbacks.""" + if self.initializeWalker is not None: + walk, root = self.initializeWalker(expr) + if not walk: + return root + elif root is None: + root = expr + else: + root = expr + + try: + result = self._process_node(root, RECURSION_LIMIT) + _nonrecursive = None + except RevertToNonrecursive: + ptr = (None,) + self.recursion_stack.pop() + while self.recursion_stack: + ptr = (ptr,) + self.recursion_stack.pop() + self.recursion_stack = None + _nonrecursive = self._nonrecursive_walker_loop, ptr + except RecursionError: + logger.warning( + 'Unexpected RecursionError walking an expression tree.', + extra={'id': 'W1003'}, + ) + _nonrecursive = self.walk_expression_nonrecursive, expr + + if _nonrecursive is not None: + return _nonrecursive[0](_nonrecursive[1]) + + if self.finalizeResult is not None: + return self.finalizeResult(result) + else: + return result + + def _compute_actual_recursion_limit(self): + recursion_limit = ( + sys.getrecursionlimit() - get_stack_depth() - 2 * RECURSION_LIMIT + ) + if recursion_limit <= RECURSION_LIMIT: + self.recursion_stack = [] + raise RevertToNonrecursive() + return recursion_limit + + def _process_node_general(self, node, recursion_limit): + """Recursive routine for processing nodes with general callbacks + + This is the "general" implementation of the + StreamBasedExpressionVisitor node processor that can handle any + combination of registered callback functions. + + """ + if not recursion_limit: + recursion_limit = self._compute_actual_recursion_limit() + else: + recursion_limit -= 1 + + if self.enterNode is not None: + tmp = self.enterNode(node) + if tmp is None: + args = data = None + else: + args, data = tmp + else: + args = None + data = [] + if args is None: + if type(node) in nonpyomo_leaf_types or not node.is_expression_type(): + args = () + else: + args = node.args + + # Because we do not require the args to be a context manager, we + # will mock up the "with args" using a try-finally. + context_manager = hasattr(args, '__enter__') + if context_manager: + args.__enter__() + + try: + descend = True + child_idx = -1 + # Note: this relies on iter(iterator) returning the + # iterator. This seems to hold for all common iterators + # (list, tuple, generator, etc) + arg_iter = iter(args) + for child in arg_iter: + child_idx += 1 + if self.beforeChild is not None: + tmp = self.beforeChild(node, child, child_idx) + if tmp is None: + descend = True + else: + descend, child_result = tmp + + if descend: + child_result = self._process_node(child, recursion_limit) + + if self.acceptChildResult is not None: + data = self.acceptChildResult(node, data, child_result, child_idx) + elif data is not None: + data.append(child_result) + + if self.afterChild is not None: + self.afterChild(node, child, child_idx) + except RevertToNonrecursive: + self._recursive_frame_to_nonrecursive_stack(locals()) + context_manager = False + raise + finally: + if context_manager: + args.__exit__(None, None, None) + + # We are done with this node. Call exitNode to compute + # any result + if self.exitNode is not None: + return self.exitNode(node, data) + else: + return data + + def _process_node_bex(self, node, recursion_limit): + """Recursive routine for processing nodes with only 'bex' callbacks + + This is a special-case implementation of the "general" + StreamBasedExpressionVisitor node processor for the case that + only beforeChild, enterNode, and exitNode are defined (see + also the definition of the client_methods dict). + + """ + if not recursion_limit: + recursion_limit = self._compute_actual_recursion_limit() + else: + recursion_limit -= 1 + + tmp = self.enterNode(node) + if tmp is None: + args = data = None + else: + args, data = tmp + if args is None: + if type(node) in nonpyomo_leaf_types or not node.is_expression_type(): + args = () + else: + args = node.args + + # Because we do not require the args to be a context manager, we + # will mock up the "with args" using a try-finally. + context_manager = hasattr(args, '__enter__') + if context_manager: + args.__enter__() + + try: + child_idx = -1 + # Note: this relies on iter(iterator) returning the + # iterator. This seems to hold for all common iterators + # (list, tuple, generator, etc) + arg_iter = iter(args) + for child in arg_iter: + child_idx += 1 + tmp = self.beforeChild(node, child, child_idx) + if tmp is None: + descend = True + else: + descend, child_result = tmp + + if descend: + data.append(self._process_node(child, recursion_limit)) + else: + data.append(child_result) + except RevertToNonrecursive: + self._recursive_frame_to_nonrecursive_stack(locals()) + context_manager = False + raise + finally: + if context_manager: + args.__exit__(None, None, None) + + # We are done with this node. Call exitNode to compute + # any result + return self.exitNode(node, data) + + def _process_node_bx(self, node, recursion_limit): + """Recursive routine for processing nodes with only 'bx' callbacks + + This is a special-case implementation of the "general" + StreamBasedExpressionVisitor node processor for the case that + only beforeChild and exitNode are defined (see also the + definition of the client_methods dict). + + """ + if not recursion_limit: + recursion_limit = self._compute_actual_recursion_limit() + else: + recursion_limit -= 1 + + if type(node) in nonpyomo_leaf_types or not node.is_expression_type(): + args = () + else: + args = node.args + data = [] + + try: + child_idx = -1 + # Note: this relies on iter(iterator) returning the + # iterator. This seems to hold for all common iterators + # (list, tuple, generator, etc) + arg_iter = iter(args) + for child in arg_iter: + child_idx += 1 + tmp = self.beforeChild(node, child, child_idx) + if tmp is None: + descend = True + else: + descend, child_result = tmp + if descend: + data.append(self._process_node(child, recursion_limit)) + else: + data.append(child_result) + except RevertToNonrecursive: + self._recursive_frame_to_nonrecursive_stack(locals()) + raise + finally: + pass + + # We are done with this node. Call exitNode to compute + # any result + return self.exitNode(node, data) + + def _recursive_frame_to_nonrecursive_stack(self, local): + child_idx = local['child_idx'] + _arg_list = [None] * child_idx + _arg_list.append(local['child']) + _arg_list.extend(local['arg_iter']) + if not self.recursion_stack: + # For the deepest stack frame, the recursion limit hit + # as we started to enter the child. As we haven't + # started processing it yet, we need to decrement + # child_idx so that it is revisited + child_idx -= 1 + self.recursion_stack.append( + (local['node'], _arg_list, len(_arg_list) - 1, local['data'], child_idx) + ) + + def walk_expression_nonrecursive(self, expr): + """Walk an expression, calling registered callbacks.""" + # + # This walker uses a linked list to store the stack (instead of + # an array). The nodes of the linked list are 6-member tuples: + # + # ( pointer to parent, + # expression node, + # tuple/list of child nodes (arguments), + # number of child nodes (arguments), + # data object to aggregate results from child nodes, + # current child node index ) + # + # The walker only needs a single pointer to the end of the list + # (ptr). The beginning of the list is indicated by a None + # parent pointer. + # + if self.initializeWalker is not None: + walk, result = self.initializeWalker(expr) + if not walk: + return result + elif result is not None: + expr = result + if self.enterNode is not None: + tmp = self.enterNode(expr) + if tmp is None: + args = data = None + else: + args, data = tmp + else: + args = None + data = [] + if args is None: + if type(expr) in nonpyomo_leaf_types or not expr.is_expression_type(): + args = () + else: + args = expr.args + if hasattr(args, '__enter__'): + args.__enter__() + node = expr + # Note that because we increment child_idx just before fetching + # the child node, it must be initialized to -1, and ptr[3] must + # always be *one less than* the number of arguments + return self._nonrecursive_walker_loop( + (None, node, args, len(args) - 1, data, -1) + ) + + def _nonrecursive_walker_loop(self, ptr): + _, node, args, _, data, child_idx = ptr + try: + while 1: + if child_idx < ptr[3]: + # Increment the child index pointer here for + # consistency. Note that this means that for the bulk + # of the time, 'child_idx' will not match the value of + # ptr[5]. This provides a modest performance + # improvement, as we only have to recreate the ptr tuple + # just before we descend further into the tree (i.e., we + # avoid recreating the tuples for the special case where + # beforeChild indicates that we should not descend + # further). + child_idx += 1 + # This node still has children to process + child = ptr[2][child_idx] + + # Notify this node that we are about to descend into a + # child. + if self.beforeChild is not None: + tmp = self.beforeChild(node, child, child_idx) + if tmp is None: + descend = True + child_result = None + else: + descend, child_result = tmp + if not descend: + # We are aborting processing of this child node. + # Tell this node to accept the child result and + # we will move along + if self.acceptChildResult is not None: + data = self.acceptChildResult( + node, data, child_result, child_idx + ) + elif data is not None: + data.append(child_result) + # And let the node know that we are done with a + # child node + if self.afterChild is not None: + self.afterChild(node, child, child_idx) + # Jump to the top to continue processing the + # next child node + continue + + # Update the child argument counter in the stack. + # Because we are using tuples, we need to recreate the + # "ptr" object (linked list node) + ptr = ptr[:4] + (data, child_idx) + + # We are now going to actually enter this node. The + # node will tell us the list of its child nodes that we + # need to process + if self.enterNode is not None: + tmp = self.enterNode(child) + if tmp is None: + args = data = None + else: + args, data = tmp + else: + args = None + data = [] + if args is None: + if ( + type(child) in nonpyomo_leaf_types + or not child.is_expression_type() + ): + # Leaves (either non-pyomo types or + # non-Expressions) have no child arguments, so + # are just put on the stack + args = () + else: + args = child.args + if hasattr(args, '__enter__'): + args.__enter__() + node = child + child_idx = -1 + ptr = (ptr, node, args, len(args) - 1, data, child_idx) + + else: # child_idx == ptr[3]: + # We are done with this node. Call exitNode to compute + # any result + if hasattr(ptr[2], '__exit__'): + ptr[2].__exit__(None, None, None) + if self.exitNode is not None: + node_result = self.exitNode(node, data) + else: + node_result = data + + # Pop the node off the linked list + ptr = ptr[0] + # If we have returned to the beginning, return the final + # answer + if ptr is None: + if self.finalizeResult is not None: + return self.finalizeResult(node_result) + else: + return node_result + # Not done yet, update node to point to the new active + # node + node, child = ptr[1], node + data = ptr[4] + child_idx = ptr[5] + + # We need to alert the node to accept the child's result: + if self.acceptChildResult is not None: + data = self.acceptChildResult( + node, data, node_result, child_idx + ) + elif data is not None: + data.append(node_result) + + # And let the node know that we are done with a child node + if self.afterChild is not None: + self.afterChild(node, child, child_idx) + + finally: + while ptr is not None: + if hasattr(ptr[2], '__exit__'): + ptr[2].__exit__(None, None, None) + ptr = ptr[0] + + -- 2.30.2