1# ___________________________________________________________________________ 2# 3# Pyomo: Python Optimization Modeling Objects 4# Copyright 2017 National Technology and Engineering Solutions of Sandia, LLC 5# Under the terms of Contract DE-NA0003525 with National Technology and 6# Engineering Solutions of Sandia, LLC, the U.S. Government retains certain 7# rights in this software. 8# This software is distributed under the 3-clause BSD License. 9# ___________________________________________________________________________ 10 11from __future__ import division 12 13import inspect 14import logging 15from copy import deepcopy 16from collections import deque 17 18logger = logging.getLogger('pyomo.core') 19 20from .symbol_map import SymbolMap 21from . import expr_common as common 22from .expr_errors import TemplateExpressionError 23from pyomo.common.deprecation import deprecation_warning 24from pyomo.core.expr.numvalue import ( 25 nonpyomo_leaf_types, 26 native_numeric_types, 27 value,) 28 29 30# NOTE: This module also has dependencies on numeric_expr; however, to 31# avoid circular dependencies, we will NOT import them here. Instead, 32# until we can resolve the circular dependencies, they will be injected 33# into this module by the .current module (which must be imported 34# *after* numeric_expr, logocal_expr, and this module. 35 36 37#------------------------------------------------------- 38# 39# Visitor Logic 40# 41#------------------------------------------------------- 42 43class StreamBasedExpressionVisitor(object): 44 """This class implements a generic stream-based expression walker. 45 46 This visitor walks an expression tree using a depth-first strategy 47 and generates a full event stream similar to other tree visitors 48 (e.g., the expat XML parser). The following events are triggered 49 through callback functions as the traversal enters and leaves nodes 50 in the tree: 51 52 initializeWalker(expr) -> walk, result 53 enterNode(N1) -> args, data 54 {for N2 in args:} 55 beforeChild(N1, N2) -> descend, child_result 56 enterNode(N2) -> N2_args, N2_data 57 [...] 58 exitNode(N2, n2_data) -> child_result 59 acceptChildResult(N1, data, child_result) -> data 60 afterChild(N1, N2) -> None 61 exitNode(N1, data) -> N1_result 62 finalizeWalker(result) -> result 63 64 Individual event callbacks match the following signatures: 65 66 walk, result = initializeWalker(self, expr): 67 68 initializeWalker() is called to set the walker up and perform 69 any preliminary processing on the root node. The method returns 70 a flag indicating if the tree should be walked and a result. If 71 `walk` is True, then result is ignored. If `walk` is False, 72 then `result` is returned as the final result from the walker, 73 bypassing all other callbacks (including finalizeResult). 74 75 args, data = enterNode(self, node): 76 77 enterNode() is called when the walker first enters a node (from 78 above), and is passed the node being entered. It is expected to 79 return a tuple of child `args` (as either a tuple or list) and a 80 user-specified data structure for collecting results. If None 81 is returned for args, the node's args attribute is used for 82 expression types and the empty tuple for leaf nodes. Returning 83 None is equivalent to returning (None,None). If the callback is 84 not defined, the default behavior is equivalent to returning 85 (None, []). 86 87 node_result = exitNode(self, node, data): 88 89 exitNode() is called after the node is completely processed (as 90 the walker returns up the tree to the parent node). It is 91 passed the node and the results data structure (defined by 92 enterNode() and possibly further modified by 93 acceptChildResult()), and is expected to return the "result" for 94 this node. If not specified, the default action is to return 95 the data object from enterNode(). 96 97 descend, child_result = beforeChild(self, node, child, child_idx): 98 99 beforeChild() is called by a node for every child before 100 entering the child node. The node, child node, and child index 101 (position in the args list from enterNode()) are passed as 102 arguments. beforeChild should return a tuple (descend, 103 child_result). If descend is False, the child node will not be 104 entered and the value returned to child_result will be passed to 105 the node's acceptChildResult callback. Returning None is 106 equivalent to (True, None). The default behavior if not 107 specified is equivalent to (True, None). 108 109 data = acceptChildResult(self, node, data, child_result, child_idx): 110 111 acceptChildResult() is called for each child result being 112 returned to a node. This callback is responsible for recording 113 the result for later processing or passing up the tree. It is 114 passed the node, result data structure (see enterNode()), child 115 result, and the child index (position in args from enterNode()). 116 The data structure (possibly modified or replaced) must be 117 returned. If acceptChildResult is not specified, it does 118 nothing if data is None, otherwise it calls data.append(result). 119 120 afterChild(self, node, child, child_idx): 121 122 afterChild() is called by a node for every child node 123 immediately after processing the node is complete before control 124 moves to the next child or up to the parent node. The node, 125 child node, an child index (position in args from enterNode()) 126 are passed, and nothing is returned. If afterChild is not 127 specified, no action takes place. 128 129 finalizeResult(self, result): 130 131 finalizeResult() is called once after the entire expression tree 132 has been walked. It is passed the result returned by the root 133 node exitNode() callback. If finalizeResult is not specified, 134 the walker returns the result obtained from the exitNode 135 callback on the root node. 136 137 Clients interact with this class by either deriving from it and 138 implementing the necessary callbacks (see above), assigning callable 139 functions to an instance of this class, or passing the callback 140 functions as arguments to this class' constructor. 141 142 """ 143 144 # The list of event methods that can either be implemented by 145 # derived classes or specified as callback functions to the class 146 # constructor: 147 client_methods = ('enterNode','exitNode','beforeChild','afterChild', 148 'acceptChildResult','initializeWalker','finalizeResult') 149 def __init__(self, **kwds): 150 # This is slightly tricky: We want derived classes to be able to 151 # override the "None" defaults here, and for keyword arguments 152 # to override both. The hasattr check prevents the "None" 153 # defaults from overriding attributes or methods defined on 154 # derived classes. 155 for field in self.client_methods: 156 if field in kwds: 157 setattr(self, field, kwds.pop(field)) 158 elif not hasattr(self, field): 159 setattr(self, field, None) 160 if kwds: 161 raise RuntimeError("Unrecognized keyword arguments: %s" % (kwds,)) 162 163 # Handle deprecated APIs 164 _fcns = (('beforeChild',2), ('acceptChildResult',3), ('afterChild',2)) 165 for name, nargs in _fcns: 166 fcn = getattr(self, name) 167 if fcn is None: 168 continue 169 _args = inspect.getfullargspec(fcn) 170 _self_arg = 1 if inspect.ismethod(fcn) else 0 171 if len(_args.args) == nargs + _self_arg and _args.varargs is None: 172 deprecation_warning( 173 "Note that the API for the StreamBasedExpressionVisitor " 174 "has changed to include the child index for the %s() " 175 "method. Please update your walker callbacks." % (name,), 176 version='5.7.0') 177 def wrap(fcn, nargs): 178 def wrapper(*args): 179 return fcn(*args[:nargs]) 180 return wrapper 181 setattr(self, name, wrap(fcn, nargs)) 182 183 184 def walk_expression(self, expr): 185 """Walk an expression, calling registered callbacks. 186 """ 187 # 188 # This walker uses a linked list to store the stack (instead of 189 # an array). The nodes of the linked list are 6-member tuples: 190 # 191 # ( pointer to parent, 192 # expression node, 193 # tuple/list of child nodes (arguments), 194 # number of child nodes (arguments), 195 # data object to aggregate results from child nodes, 196 # current child node index ) 197 # 198 # The walker only needs a single pointer to the end of the list 199 # (ptr). The beginning of the list is indicated by a None 200 # parent pointer. 201 # 202 if self.initializeWalker is not None: 203 walk, result = self.initializeWalker(expr) 204 if not walk: 205 return result 206 if self.enterNode is not None: 207 tmp = self.enterNode(expr) 208 if tmp is None: 209 args = data = None 210 else: 211 args, data = tmp 212 else: 213 args = None 214 data = [] 215 if args is None: 216 if type(expr) in nonpyomo_leaf_types \ 217 or not expr.is_expression_type(): 218 args = () 219 else: 220 args = expr.args 221 if hasattr(args, '__enter__'): 222 args.__enter__() 223 node = expr 224 # Note that because we increment child_idx just before fetching 225 # the child node, it must be initialized to -1, and ptr[3] must 226 # always be *one less than* the number of arguments 227 child_idx = -1 228 ptr = (None, node, args, len(args)-1, data, child_idx) 229 230 try: 231 while 1: 232 if child_idx < ptr[3]: 233 # Increment the child index pointer here for 234 # consistency. Note that this means that for the bulk 235 # of the time, 'child_idx' will not match the value of 236 # ptr[5]. This provides a modest performance 237 # improvement, as we only have to recreate the ptr tuple 238 # just before we descend further into the tree (i.e., we 239 # avoid recreating the tuples for the special case where 240 # beforeChild indicates that we should not descend 241 # further). 242 child_idx += 1 243 # This node still has children to process 244 child = ptr[2][child_idx] 245 246 # Notify this node that we are about to descend into a 247 # child. 248 if self.beforeChild is not None: 249 tmp = self.beforeChild(node, child, child_idx) 250 if tmp is None: 251 descend = True 252 child_result = None 253 else: 254 descend, child_result = tmp 255 if not descend: 256 # We are aborting processing of this child node. 257 # Tell this node to accept the child result and 258 # we will move along 259 if self.acceptChildResult is not None: 260 data = self.acceptChildResult( 261 node, data, child_result, child_idx) 262 elif data is not None: 263 data.append(child_result) 264 # And let the node know that we are done with a 265 # child node 266 if self.afterChild is not None: 267 self.afterChild(node, child, child_idx) 268 # Jump to the top to continue processing the 269 # next child node 270 continue 271 272 # Update the child argument counter in the stack. 273 # Because we are using tuples, we need to recreate the 274 # "ptr" object (linked list node) 275 ptr = ptr[:4] + (data, child_idx,) 276 277 # We are now going to actually enter this node. The 278 # node will tell us the list of its child nodes that we 279 # need to process 280 if self.enterNode is not None: 281 tmp = self.enterNode(child) 282 if tmp is None: 283 args = data = None 284 else: 285 args, data = tmp 286 else: 287 args = None 288 data = [] 289 if args is None: 290 if type(child) in nonpyomo_leaf_types \ 291 or not child.is_expression_type(): 292 # Leaves (either non-pyomo types or 293 # non-Expressions) have no child arguments, so 294 # are just put on the stack 295 args = () 296 else: 297 args = child.args 298 if hasattr(args, '__enter__'): 299 args.__enter__() 300 node = child 301 child_idx = -1 302 ptr = (ptr, node, args, len(args)-1, data, child_idx) 303 304 else: # child_idx == ptr[3]: 305 # We are done with this node. Call exitNode to compute 306 # any result 307 if hasattr(ptr[2], '__exit__'): 308 ptr[2].__exit__(None, None, None) 309 if self.exitNode is not None: 310 node_result = self.exitNode(node, data) 311 else: 312 node_result = data 313 314 # Pop the node off the linked list 315 ptr = ptr[0] 316 # If we have returned to the beginning, return the final 317 # answer 318 if ptr is None: 319 if self.finalizeResult is not None: 320 return self.finalizeResult(node_result) 321 else: 322 return node_result 323 # Not done yet, update node to point to the new active 324 # node 325 node, child = ptr[1], node 326 data = ptr[4] 327 child_idx = ptr[5] 328 329 # We need to alert the node to accept the child's result: 330 if self.acceptChildResult is not None: 331 data = self.acceptChildResult( 332 node, data, node_result, child_idx) 333 elif data is not None: 334 data.append(node_result) 335 336 # And let the node know that we are done with a child node 337 if self.afterChild is not None: 338 self.afterChild(node, child, child_idx) 339 340 finally: 341 while ptr is not None: 342 if hasattr(ptr[2], '__exit__'): 343 ptr[2].__exit__(None, None, None) 344 ptr = ptr[0] 345 346class SimpleExpressionVisitor(object): 347 348 """ 349 Note: 350 This class is a customization of the PyUtilib :class:`SimpleVisitor 351 <pyutilib.misc.visitor.SimpleVisitor>` class that is tailored 352 to efficiently walk Pyomo expression trees. However, this class 353 is not a subclass of the PyUtilib :class:`SimpleVisitor 354 <pyutilib.misc.visitor.SimpleVisitor>` class because all key methods 355 are reimplemented. 356 """ 357 358 def visit(self, node): #pragma: no cover 359 """ 360 Visit a node in an expression tree and perform some operation on 361 it. 362 363 This method should be over-written by a user 364 that is creating a sub-class. 365 366 Args: 367 node: a node in an expression tree 368 369 Returns: 370 nothing 371 """ 372 pass 373 374 def finalize(self): #pragma: no cover 375 """ 376 Return the "final value" of the search. 377 378 The default implementation returns :const:`None`, because 379 the traditional visitor pattern does not return a value. 380 381 Returns: 382 The final value after the search. Default is :const:`None`. 383 """ 384 pass 385 386 def xbfs(self, node): 387 """ 388 Breadth-first search of an expression tree, 389 except that leaf nodes are immediately visited. 390 391 Note: 392 This method has the same functionality as the 393 PyUtilib :class:`SimpleVisitor.xbfs <pyutilib.misc.visitor.SimpleVisitor.xbfs>` 394 method. The difference is that this method 395 is tailored to efficiently walk Pyomo expression trees. 396 397 Args: 398 node: The root node of the expression tree that is searched. 399 400 Returns: 401 The return value is determined by the :func:`finalize` function, 402 which may be defined by the user. Defaults to :const:`None`. 403 """ 404 dq = deque([node]) 405 while dq: 406 current = dq.popleft() 407 self.visit(current) 408 #for c in self.children(current): 409 for c in current.args: 410 #if self.is_leaf(c): 411 if c.__class__ in nonpyomo_leaf_types or not c.is_expression_type() or c.nargs() == 0: 412 self.visit(c) 413 else: 414 dq.append(c) 415 return self.finalize() 416 417 def xbfs_yield_leaves(self, node): 418 """ 419 Breadth-first search of an expression tree, except that 420 leaf nodes are immediately visited. 421 422 Note: 423 This method has the same functionality as the 424 PyUtilib :class:`SimpleVisitor.xbfs_yield_leaves <pyutilib.misc.visitor.SimpleVisitor.xbfs_yield_leaves>` 425 method. The difference is that this method 426 is tailored to efficiently walk Pyomo expression trees. 427 428 Args: 429 node: The root node of the expression tree 430 that is searched. 431 432 Returns: 433 The return value is determined by the :func:`finalize` function, 434 which may be defined by the user. Defaults to :const:`None`. 435 """ 436 # 437 # If we start with a leaf, then yield it and stop iteration 438 # 439 if node.__class__ in nonpyomo_leaf_types or not node.is_expression_type() or node.nargs() == 0: 440 ans = self.visit(node) 441 if not ans is None: 442 yield ans 443 return 444 # 445 # Iterate through the tree. 446 # 447 dq = deque([node]) 448 while dq: 449 current = dq.popleft() 450 #self.visit(current) 451 #for c in self.children(current): 452 for c in current.args: 453 #if self.is_leaf(c): 454 if c.__class__ in nonpyomo_leaf_types or not c.is_expression_type() or c.nargs() == 0: 455 ans = self.visit(c) 456 if not ans is None: 457 yield ans 458 else: 459 dq.append(c) 460 461 462class ExpressionValueVisitor(object): 463 """ 464 Note: 465 This class is a customization of the PyUtilib :class:`ValueVisitor 466 <pyutilib.misc.visitor.ValueVisitor>` class that is tailored 467 to efficiently walk Pyomo expression trees. However, this class 468 is not a subclass of the PyUtilib :class:`ValueVisitor 469 <pyutilib.misc.visitor.ValueVisitor>` class because all key methods 470 are reimplemented. 471 """ 472 473 def visit(self, node, values): #pragma: no cover 474 """ 475 Visit a node in a tree and compute its value using 476 the values of its children. 477 478 This method should be over-written by a user 479 that is creating a sub-class. 480 481 Args: 482 node: a node in a tree 483 values: a list of values of this node's children 484 485 Returns: 486 The *value* for this node, which is computed using :attr:`values` 487 """ 488 pass 489 490 def visiting_potential_leaf(self, node): #pragma: no cover 491 """ 492 Visit a node and return its value if it is a leaf. 493 494 Note: 495 This method needs to be over-written for a specific 496 visitor application. 497 498 Args: 499 node: a node in a tree 500 501 Returns: 502 A tuple: ``(flag, value)``. If ``flag`` is False, 503 then the node is not a leaf and ``value`` is :const:`None`. 504 Otherwise, ``value`` is the computed value for this node. 505 """ 506 raise RuntimeError("The visiting_potential_leaf method needs to be defined.") 507 508 def finalize(self, ans): #pragma: no cover 509 """ 510 This method defines the return value for the search methods 511 in this class. 512 513 The default implementation returns the value of the 514 initial node (aka the root node), because 515 this visitor pattern computes and returns value for each 516 node to enable the computation of this value. 517 518 Args: 519 ans: The final value computed by the search method. 520 521 Returns: 522 The final value after the search. Defaults to simply 523 returning :attr:`ans`. 524 """ 525 return ans 526 527 def dfs_postorder_stack(self, node): 528 """ 529 Perform a depth-first search in postorder using a stack 530 implementation. 531 532 Note: 533 This method has the same functionality as the 534 PyUtilib :class:`ValueVisitor.dfs_postorder_stack <pyutilib.misc.visitor.ValueVisitor.dfs_postorder_stack>` 535 method. The difference is that this method 536 is tailored to efficiently walk Pyomo expression trees. 537 538 Args: 539 node: The root node of the expression tree 540 that is searched. 541 542 Returns: 543 The return value is determined by the :func:`finalize` function, 544 which may be defined by the user. 545 """ 546 flag, value = self.visiting_potential_leaf(node) 547 if flag: 548 return self.finalize(value) 549 #_stack = [ (node, self.children(node), 0, len(self.children(node)), [])] 550 _stack = [ (node, node._args_, 0, node.nargs(), [])] 551 # 552 # Iterate until the stack is empty 553 # 554 # Note: 1 is faster than True for Python 2.x 555 # 556 while 1: 557 # 558 # Get the top of the stack 559 # _obj Current expression object 560 # _argList The arguments for this expression objet 561 # _idx The current argument being considered 562 # _len The number of arguments 563 # _result The return values 564 # 565 _obj, _argList, _idx, _len, _result = _stack.pop() 566 # 567 # Iterate through the arguments 568 # 569 while _idx < _len: 570 _sub = _argList[_idx] 571 _idx += 1 572 flag, value = self.visiting_potential_leaf(_sub) 573 if flag: 574 _result.append( value ) 575 else: 576 # 577 # Push an expression onto the stack 578 # 579 _stack.append( (_obj, _argList, _idx, _len, _result) ) 580 _obj = _sub 581 #_argList = self.children(_sub) 582 _argList = _sub._args_ 583 _idx = 0 584 _len = _sub.nargs() 585 _result = [] 586 # 587 # Process the current node 588 # 589 ans = self.visit(_obj, _result) 590 if _stack: 591 # 592 # "return" the recursion by putting the return value on the end of the results stack 593 # 594 _stack[-1][-1].append( ans ) 595 else: 596 return self.finalize(ans) 597 598def replace_expressions(expr, 599 substitution_map, 600 descend_into_named_expressions=True, 601 remove_named_expressions=False): 602 """ 603 604 Parameters 605 ---------- 606 expr : Pyomo expression 607 The source expression 608 substitution_map : dict 609 A dictionary mapping object ids in the source to the replacement objects. 610 descend_into_named_expressions : bool 611 True if replacement should go into named expression objects, False to halt at 612 a named expression 613 remove_named_expressions : bool 614 True if the named expressions should be replaced with a standard expression, 615 and False if the named expression should be left in place 616 617 Returns 618 ------- 619 Pyomo expression : returns the new expression object 620 """ 621 new_expr = ExpressionReplacementVisitor( 622 substitute=substitution_map, 623 descend_into_named_expressions=descend_into_named_expressions, 624 remove_named_expressions=remove_named_expressions 625 ).dfs_postorder_stack(expr) 626 return new_expr 627 628 629class ExpressionReplacementVisitor(object): 630 """ 631 Note: 632 This class is a customization of the PyUtilib :class:`ValueVisitor 633 <pyutilib.misc.visitor.ValueVisitor>` class that is tailored 634 to support replacement of sub-trees in a Pyomo expression 635 tree. However, this class is not a subclass of the PyUtilib 636 :class:`ValueVisitor <pyutilib.misc.visitor.ValueVisitor>` 637 class because all key methods are reimplemented. 638 """ 639 640 def __init__(self, 641 substitute=None, 642 descend_into_named_expressions=True, 643 remove_named_expressions=False): 644 """ 645 Contruct a visitor that is tailored to support the 646 replacement of sub-trees in a pyomo expression tree. 647 648 Args: 649 memo (dict): A dictionary mapping object ids to 650 objects. This dictionary has the same semantics as 651 the memo object used with ``copy.deepcopy``. Defaults 652 to None, which indicates that no user-defined 653 dictionary is used. 654 """ 655 self.enter_named_expr = descend_into_named_expressions 656 self.rm_named_expr = remove_named_expressions 657 if substitute is None: 658 self.substitute = {} 659 else: 660 self.substitute = substitute 661 662 def visit(self, node, values): 663 """ 664 Visit and clone nodes that have been expanded. 665 666 Note: 667 This method normally does not need to be re-defined 668 by a user. 669 670 Args: 671 node: The node that will be cloned. 672 values (list): The list of child nodes that have been 673 cloned. These values are used to define the 674 cloned node. 675 676 Returns: 677 The cloned node. Default is to simply return the node. 678 """ 679 return node 680 681 def visiting_potential_leaf(self, node): #pragma: no cover 682 """ 683 Visit a node and return a cloned node if it is a leaf. 684 685 Note: 686 This method needs to be over-written for a specific 687 visitor application. 688 689 Args: 690 node: a node in a tree 691 692 Returns: 693 A tuple: ``(flag, value)``. If ``flag`` is False, 694 then the node is not a leaf and ``value`` is :const:`None`. 695 Otherwise, ``value`` is a cloned node. 696 """ 697 _id = id(node) 698 if _id in self.substitute: 699 return True, self.substitute[_id] 700 elif type(node) in nonpyomo_leaf_types or not node.is_expression_type(): 701 return True, node 702 elif not self.enter_named_expr and node.is_named_expression_type(): 703 return True, node 704 else: 705 return False, None 706 707 def finalize(self, ans): 708 """ 709 This method defines the return value for the search methods 710 in this class. 711 712 The default implementation returns the value of the 713 initial node (aka the root node), because 714 this visitor pattern computes and returns value for each 715 node to enable the computation of this value. 716 717 Args: 718 ans: The final value computed by the search method. 719 720 Returns: 721 The final value after the search. Defaults to simply 722 returning :attr:`ans`. 723 """ 724 return ans 725 726 def construct_node(self, node, values): 727 """ 728 Call the expression create_node_with_local_data() method. 729 """ 730 return node.create_node_with_local_data( tuple(values) ) 731 732 def dfs_postorder_stack(self, node): 733 """ 734 Perform a depth-first search in postorder using a stack 735 implementation. 736 737 This method replaces subtrees. This method detects if the 738 :func:`visit` method returns a different object. If so, then 739 the node has been replaced and search process is adapted 740 to replace all subsequent parent nodes in the tree. 741 742 Note: 743 This method has the same functionality as the 744 PyUtilib :class:`ValueVisitor.dfs_postorder_stack <pyutilib.misc.visitor.ValueVisitor.dfs_postorder_stack>` 745 method that is tailored to support the 746 replacement of sub-trees in a Pyomo expression tree. 747 748 Args: 749 node: The root node of the expression tree 750 that is searched. 751 752 Returns: 753 The return value is determined by the :func:`finalize` function, 754 which may be defined by the user. 755 """ 756 if node.__class__ is LinearExpression: 757 _argList = [node.constant] + node.linear_coefs + node.linear_vars 758 _len = len(_argList) 759 _stack = [ (node, _argList, 0, _len, [False])] 760 else: 761 flag, value = self.visiting_potential_leaf(node) 762 if flag: 763 return value 764 _stack = [ (node, node._args_, 0, node.nargs(), [False])] 765 # 766 # Iterate until the stack is empty 767 # 768 # Note: 1 is faster than True for Python 2.x 769 # 770 while 1: 771 # 772 # Get the top of the stack 773 # _obj Current expression object 774 # _argList The arguments for this expression objet 775 # _idx The current argument being considered 776 # _len The number of arguments 777 # _result The 'dirty' flag followed by return values 778 # 779 _obj, _argList, _idx, _len, _result = _stack.pop() 780 # 781 # Iterate through the arguments, entering each one 782 # 783 while _idx < _len: 784 _sub = _argList[_idx] 785 _idx += 1 786 flag, value = self.visiting_potential_leaf(_sub) 787 if flag: 788 if id(value) != id(_sub): 789 _result[0] = True 790 _result.append( value ) 791 else: 792 # 793 # Push an expression onto the stack 794 # 795 _stack.append( (_obj, _argList, _idx, _len, _result) ) 796 _obj = _sub 797 _idx = 0 798 _result = [False] 799 if _sub.__class__ is LinearExpression: 800 _argList = [_sub.constant] + _sub.linear_coefs \ 801 + _sub.linear_vars 802 _len = len(_argList) 803 else: 804 _argList = _sub._args_ 805 _len = _sub.nargs() 806 # 807 # Finalize (exit) the current node 808 # 809 # If the user has defined a visit() function in a 810 # subclass, then call that function. But if the user 811 # hasn't created a new class and we need to, then 812 # call the ExpressionReplacementVisitor.visit() function. 813 # 814 ans = self.visit(_obj, _result[1:]) 815 if ans.is_named_expression_type(): 816 if self.rm_named_expr: 817 ans = _result[1] 818 _result[0] = True 819 else: 820 _result[0] = False 821 assert(len(_result) == 2) 822 ans.expr = _result[1] 823 elif _result[0]: 824 if ans.__class__ is LinearExpression: 825 ans = _result[1] 826 nterms = (len(_result)-2)//2 827 for i in range(nterms): 828 ans += _result[2+i]*_result[2+i+nterms] 829 if id(ans) == id(_obj): 830 ans = self.construct_node(_obj, _result[1:]) 831 if ans.__class__ is MonomialTermExpression: 832 # CDL This code wass trying to determine if we needed to change the MonomialTermExpression 833 # to a ProductExpression, but it fails for the case of a MonomialExpression 834 # that has its rhs Var replaced with another MonomialExpression (and might 835 # fail for other cases as well. 836 # Rather than trying to update the logic to catch all cases, I am choosing 837 # to execute the actual product operator code instead to ensure things are 838 # consistent 839 # See WalkerTests.test_replace_expressions_with_monomial_term in test_expr_pyomo5.py 840 # to see the behavior 841 # if ( ( ans._args_[0].__class__ not in native_numeric_types 842 # and ans._args_[0].is_potentially_variable ) 843 # or 844 # ( ans._args_[1].__class__ in native_numeric_types 845 # or not ans._args_[1].is_potentially_variable() ) ): 846 # ans.__class__ = ProductExpression 847 ans = ans._args_[0] * ans._args_[1] 848 elif ans.__class__ in NPV_expression_types: 849 # For simplicity, not-potentially-variable expressions are 850 # replaced with their potentially variable counterparts. 851 ans = ans.create_potentially_variable_object() 852 elif id(ans) != id(_obj): 853 _result[0] = True 854 855 if _stack: 856 if _result[0]: 857 _stack[-1][-1][0] = True 858 # 859 # "return" the recursion by putting the return value on 860 # the end of the results stack 861 # 862 _stack[-1][-1].append( ans ) 863 else: 864 return self.finalize(ans) 865 866 867#------------------------------------------------------- 868# 869# Functions used to process expression trees 870# 871#------------------------------------------------------- 872 873# ===================================================== 874# clone_expression 875# ===================================================== 876 877def clone_expression(expr, substitute=None): 878 """A function that is used to clone an expression. 879 880 Cloning is equivalent to calling ``copy.deepcopy`` with no Block 881 scope. That is, the expression tree is duplicated, but no Pyomo 882 components (leaf nodes *or* named Expressions) are duplicated. 883 884 Args: 885 expr: The expression that will be cloned. 886 substitute (dict): A dictionary mapping object ids to 887 objects. This dictionary has the same semantics as 888 the memo object used with ``copy.deepcopy``. Defaults 889 to None, which indicates that no user-defined 890 dictionary is used. 891 892 Returns: 893 The cloned expression. 894 895 """ 896 clone_counter._count += 1 897 memo = {'__block_scope__': {id(None): False}} 898 if substitute: 899 memo.update(substitute) 900 return deepcopy(expr, memo) 901 902 903# ===================================================== 904# sizeof_expression 905# ===================================================== 906 907def sizeof_expression(expr): 908 """ 909 Return the number of nodes in the expression tree. 910 911 Args: 912 expr: The root node of an expression tree. 913 914 Returns: 915 A non-negative integer that is the number of 916 interior and leaf nodes in the expression tree. 917 """ 918 def enter(node): 919 return None, 1 920 def accept(node, data, child_result, child_idx): 921 return data + child_result 922 return StreamBasedExpressionVisitor( 923 enterNode=enter, 924 acceptChildResult=accept, 925 ).walk_expression(expr) 926 927# ===================================================== 928# evaluate_expression 929# ===================================================== 930 931class _EvaluationVisitor(ExpressionValueVisitor): 932 933 def __init__(self, exception): 934 self.exception = exception 935 936 def visit(self, node, values): 937 """ Visit nodes that have been expanded """ 938 return node._apply_operation(values) 939 940 def visiting_potential_leaf(self, node): 941 """ 942 Visiting a potential leaf. 943 944 Return True if the node is not expanded. 945 """ 946 if node.__class__ in nonpyomo_leaf_types: 947 return True, node 948 949 if node.is_expression_type(): 950 return False, None 951 952 if node.is_numeric_type(): 953 return True, value(node, exception=self.exception) 954 elif node.is_logical_type(): 955 return True, value(node, exception=self.exception) 956 else: 957 return True, node 958 959 960 961 962class FixedExpressionError(Exception): 963 964 def __init__(self, *args, **kwds): 965 super(FixedExpressionError, self).__init__(*args, **kwds) 966 967 968class NonConstantExpressionError(Exception): 969 970 def __init__(self, *args, **kwds): 971 super(NonConstantExpressionError, self).__init__(*args, **kwds) 972 973 974class _EvaluateConstantExpressionVisitor(ExpressionValueVisitor): 975 976 def visit(self, node, values): 977 """ Visit nodes that have been expanded """ 978 return node._apply_operation(values) 979 980 def visiting_potential_leaf(self, node): 981 """ 982 Visiting a potential leaf. 983 984 Return True if the node is not expanded. 985 """ 986 if node.__class__ in nonpyomo_leaf_types: 987 return True, node 988 989 if node.is_expression_type(): 990 return False, None 991 992 if node.is_numeric_type(): 993 # Get the object value. This will also cause templates to 994 # raise TemplateExpressionErrors 995 try: 996 val = value(node) 997 except TemplateExpressionError: 998 raise 999 except: 1000 # Uninitialized Var/Param objects should be given the 1001 # opportunity to map the error to a NonConstant / Fixed 1002 # expression error 1003 if not node.is_fixed(): 1004 raise NonConstantExpressionError() 1005 if not node.is_constant(): 1006 raise FixedExpressionError() 1007 raise 1008 1009 if not node.is_fixed(): 1010 raise NonConstantExpressionError() 1011 if not node.is_constant(): 1012 raise FixedExpressionError() 1013 return True, val 1014 1015 return True, node 1016 1017 1018def evaluate_expression(exp, exception=True, constant=False): 1019 """Evaluate the value of the expression. 1020 1021 Args: 1022 expr: The root node of an expression tree. 1023 exception (bool): A flag that indicates whether 1024 exceptions are raised. If this flag is 1025 :const:`False`, then an exception that 1026 occurs while evaluating the expression 1027 is caught and the return value is :const:`None`. 1028 Default is :const:`True`. 1029 constant (bool): If True, constant expressions are 1030 evaluated and returned but nonconstant expressions 1031 raise either FixedExpressionError or 1032 NonconstantExpressionError (default=False). 1033 1034 Returns: 1035 A floating point value if the expression evaluates 1036 normally, or :const:`None` if an exception occurs 1037 and is caught. 1038 1039 """ 1040 if constant: 1041 visitor = _EvaluateConstantExpressionVisitor() 1042 else: 1043 visitor = _EvaluationVisitor(exception=exception) 1044 try: 1045 return visitor.dfs_postorder_stack(exp) 1046 1047 except ( TemplateExpressionError, ValueError, TypeError, 1048 NonConstantExpressionError, FixedExpressionError ): 1049 # Errors that we want to be able to suppress: 1050 # 1051 # TemplateExpressionError: raised when generating expression 1052 # templates 1053 # FixedExpressionError, NonConstantExpressionError: raised 1054 # when processing expressions that are expected to be fixed 1055 # (e.g., indices) 1056 # ValueError: "standard" expression value errors 1057 # TypeError: This can be raised in Python3 when evaluating a 1058 # operation returns a complex number (e.g., sqrt(-1)) 1059 if exception: 1060 raise 1061 return None 1062 1063 1064# ===================================================== 1065# identify_components 1066# ===================================================== 1067 1068class _ComponentVisitor(SimpleExpressionVisitor): 1069 1070 def __init__(self, types): 1071 self.seen = set() 1072 if types.__class__ is set: 1073 self.types = types 1074 else: 1075 self.types = set(types) 1076 1077 def visit(self, node): 1078 if node.__class__ in self.types: 1079 if id(node) in self.seen: 1080 return 1081 self.seen.add(id(node)) 1082 return node 1083 1084 1085def identify_components(expr, component_types): 1086 """ 1087 A generator that yields a sequence of nodes 1088 in an expression tree that belong to a specified set. 1089 1090 Args: 1091 expr: The root node of an expression tree. 1092 component_types (set or list): A set of class 1093 types that will be matched during the search. 1094 1095 Yields: 1096 Each node that is found. 1097 """ 1098 # 1099 # OPTIONS: 1100 # component_types - set (or list) if class types to find 1101 # in the expression. 1102 # 1103 visitor = _ComponentVisitor(component_types) 1104 yield from visitor.xbfs_yield_leaves(expr) 1105 1106 1107# ===================================================== 1108# identify_variables 1109# ===================================================== 1110 1111class _VariableVisitor(SimpleExpressionVisitor): 1112 1113 def __init__(self): 1114 self.seen = set() 1115 1116 def visit(self, node): 1117 if node.__class__ in nonpyomo_leaf_types: 1118 return 1119 1120 if node.is_variable_type(): 1121 if id(node) in self.seen: 1122 return 1123 self.seen.add(id(node)) 1124 return node 1125 1126 if node.is_expression_type() and isinstance(node, LinearExpression): 1127 if id(node) in self.seen: 1128 return 1129 self.seen.add(id(node)) 1130 1131 def unique_vars_generator(): 1132 for var in node.linear_vars: 1133 if id(var) in self.seen: 1134 continue 1135 self.seen.add(id(var)) 1136 yield var 1137 return tuple(v for v in unique_vars_generator()) 1138 1139 1140def identify_variables(expr, include_fixed=True): 1141 """ 1142 A generator that yields a sequence of variables 1143 in an expression tree. 1144 1145 Args: 1146 expr: The root node of an expression tree. 1147 include_fixed (bool): If :const:`True`, then 1148 this generator will yield variables whose 1149 value is fixed. Defaults to :const:`True`. 1150 1151 Yields: 1152 Each variable that is found. 1153 """ 1154 visitor = _VariableVisitor() 1155 if include_fixed: 1156 for v in visitor.xbfs_yield_leaves(expr): 1157 if isinstance(v, tuple): 1158 yield from v 1159 else: 1160 yield v 1161 else: 1162 for v in visitor.xbfs_yield_leaves(expr): 1163 if isinstance(v, tuple): 1164 for v_i in v: 1165 if not v_i.is_fixed(): 1166 yield v_i 1167 else: 1168 if not v.is_fixed(): 1169 yield v 1170 1171 1172# ===================================================== 1173# identify_mutable_parameters 1174# ===================================================== 1175 1176class _MutableParamVisitor(SimpleExpressionVisitor): 1177 1178 def __init__(self): 1179 self.seen = set() 1180 1181 def visit(self, node): 1182 if node.__class__ in nonpyomo_leaf_types: 1183 return 1184 1185 # TODO: Confirm that this has the right semantics 1186 if (not node.is_variable_type() and node.is_fixed() 1187 and not node.is_constant()): 1188 if id(node) in self.seen: 1189 return 1190 self.seen.add(id(node)) 1191 return node 1192 1193 1194def identify_mutable_parameters(expr): 1195 """ 1196 A generator that yields a sequence of mutable 1197 parameters in an expression tree. 1198 1199 Args: 1200 expr: The root node of an expression tree. 1201 1202 Yields: 1203 Each mutable parameter that is found. 1204 """ 1205 visitor = _MutableParamVisitor() 1206 yield from visitor.xbfs_yield_leaves(expr) 1207 1208 1209# ===================================================== 1210# polynomial_degree 1211# ===================================================== 1212 1213class _PolynomialDegreeVisitor(ExpressionValueVisitor): 1214 1215 def visit(self, node, values): 1216 """ Visit nodes that have been expanded """ 1217 return node._compute_polynomial_degree(values) 1218 1219 def visiting_potential_leaf(self, node): 1220 """ 1221 Visiting a potential leaf. 1222 1223 Return True if the node is not expanded. 1224 """ 1225 if node.__class__ in nonpyomo_leaf_types: 1226 return True, 0 1227 1228 if node.is_expression_type(): 1229 return False, None 1230 1231 if node.is_numeric_type(): 1232 return True, 0 if node.is_fixed() else 1 1233 else: 1234 return True, node 1235 1236 1237def polynomial_degree(node): 1238 """ 1239 Return the polynomial degree of the expression. 1240 1241 Args: 1242 node: The root node of an expression tree. 1243 1244 Returns: 1245 A non-negative integer that is the polynomial 1246 degree if the expression is polynomial, or :const:`None` otherwise. 1247 """ 1248 visitor = _PolynomialDegreeVisitor() 1249 return visitor.dfs_postorder_stack(node) 1250 1251 1252# ===================================================== 1253# _expression_is_fixed 1254# ===================================================== 1255 1256class _IsFixedVisitor(ExpressionValueVisitor): 1257 """ 1258 NOTE: This doesn't check if combiner logic is 1259 all or any and short-circuit the test. It's 1260 not clear that that is an important optimization. 1261 """ 1262 1263 def visit(self, node, values): 1264 """ Visit nodes that have been expanded """ 1265 return node._is_fixed(values) 1266 1267 def visiting_potential_leaf(self, node): 1268 """ 1269 Visiting a potential leaf. 1270 1271 Return True if the node is not expanded. 1272 """ 1273 if node.__class__ in nonpyomo_leaf_types: 1274 return True, True 1275 1276 elif node.is_expression_type(): 1277 return False, None 1278 1279 elif node.is_numeric_type(): 1280 return True, node.is_fixed() 1281 1282 return True, node 1283 1284 1285def _expression_is_fixed(node): 1286 """ 1287 Return the polynomial degree of the expression. 1288 1289 Args: 1290 node: The root node of an expression tree. 1291 1292 Returns: 1293 A non-negative integer that is the polynomial 1294 degree if the expression is polynomial, or :const:`None` otherwise. 1295 """ 1296 visitor = _IsFixedVisitor() 1297 return visitor.dfs_postorder_stack(node) 1298 1299 1300# ===================================================== 1301# expression_to_string 1302# ===================================================== 1303 1304class _ToStringVisitor(ExpressionValueVisitor): 1305 1306 def __init__(self, verbose, smap, compute_values): 1307 super(_ToStringVisitor, self).__init__() 1308 self.verbose = verbose 1309 self.smap = smap 1310 self.compute_values = compute_values 1311 1312 def visit(self, node, values): 1313 """ Visit nodes that have been expanded """ 1314 tmp = [] 1315 for i,val in enumerate(values): 1316 arg = node._args_[i] 1317 1318 if arg is None: 1319 tmp.append('Undefined') # TODO: coverage 1320 elif arg.__class__ in native_numeric_types: 1321 tmp.append(val) 1322 elif arg.__class__ in nonpyomo_leaf_types: 1323 tmp.append("'{0}'".format(val)) 1324 else: 1325 parens = False 1326 if not self.verbose and arg.is_expression_type(): 1327 if node._precedence() < arg._precedence(): 1328 parens = True 1329 elif node._precedence() == arg._precedence(): 1330 if i == 0: 1331 parens = node._associativity() != 1 1332 elif i == len(node._args_)-1: 1333 parens = node._associativity() != -1 1334 else: 1335 parens = True 1336 if parens: 1337 tmp.append("({0})".format(val)) 1338 else: 1339 tmp.append(val) 1340 1341 return node._to_string(tmp, self.verbose, self.smap, self.compute_values) 1342 1343 def visiting_potential_leaf(self, node): 1344 """ 1345 Visiting a potential leaf. 1346 1347 Return True if the node is not expanded. 1348 """ 1349 if node is None: 1350 return True, None # TODO: coverage 1351 1352 if node.__class__ in nonpyomo_leaf_types: 1353 return True, str(node) 1354 1355 if node.is_expression_type(): 1356 return False, None 1357 1358 if node.is_variable_type(): 1359 if not node.fixed: 1360 return True, node.to_string(verbose=self.verbose, smap=self.smap, compute_values=False) 1361 return True, node.to_string(verbose=self.verbose, smap=self.smap, compute_values=self.compute_values) 1362 1363 if hasattr(node, 'to_string'): 1364 return True, node.to_string(verbose=self.verbose, smap=self.smap, compute_values=self.compute_values) 1365 else: 1366 return True, str(node) 1367 1368 1369def expression_to_string(expr, verbose=None, labeler=None, smap=None, compute_values=False): 1370 """ 1371 Return a string representation of an expression. 1372 1373 Args: 1374 expr: The root node of an expression tree. 1375 verbose (bool): If :const:`True`, then the output is 1376 a nested functional form. Otherwise, the output 1377 is an algebraic expression. Default is :const:`False`. 1378 labeler: If specified, this labeler is used to label 1379 variables in the expression. 1380 smap: If specified, this :class:`SymbolMap <pyomo.core.expr.symbol_map.SymbolMap>` is 1381 used to cache labels. 1382 compute_values (bool): If :const:`True`, then 1383 parameters and fixed variables are evaluated before the 1384 expression string is generated. Default is :const:`False`. 1385 1386 Returns: 1387 A string representation for the expression. 1388 """ 1389 verbose = common.TO_STRING_VERBOSE if verbose is None else verbose 1390 # 1391 # Setup the symbol map 1392 # 1393 if labeler is not None: 1394 if smap is None: 1395 smap = SymbolMap() 1396 smap.default_labeler = labeler 1397 # 1398 # Create and execute the visitor pattern 1399 # 1400 visitor = _ToStringVisitor(verbose, smap, compute_values) 1401 return visitor.dfs_postorder_stack(expr) 1402