/usr/lib/python2.7/dist-packages/ufl/algorithms/traversal.py is in python-ufl 1.4.0-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 | """This module contains algorithms for traversing expression trees in different ways."""
# Copyright (C) 2008-2014 Martin Sandve Alnes and Anders Logg
#
# This file is part of UFL.
#
# UFL is free software: you can redistribute it and/or modify
# it under the terms of the GNU Lesser General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# UFL is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public License
# along with UFL. If not, see <http://www.gnu.org/licenses/>.
#
# Modified by Anders Logg, 2008
from ufl.log import error
from ufl.assertions import ufl_assert
from ufl.expr import Expr
from ufl.terminal import Terminal
from ufl.integral import Integral
from ufl.form import Form
#--- Traversal utilities ---
def iter_expressions(a):
"""Utility function to handle Form, Integral and any Expr
the same way when inspecting expressions.
Returns an iterable over Expr instances:
- a is an Expr: (a,)
- a is an Integral: the integrand expression of a
- a is a Form: all integrand expressions of all integrals
"""
if isinstance(a, Form):
return (itg._integrand for itg in a.integrals())
elif isinstance(a, Integral):
return (a._integrand,)
elif isinstance(a, Expr):
return (a,)
error("Not an UFL type: %s" % str(type(a)))
# Slow recursive version of traverse_terminals, kept here for illustration:
def __old_traverse_terminals(expr):
if isinstance(expr, Terminal):
yield expr
else:
for o in expr.operands():
for t in traverse_terminals(o):
yield t
# Faster (factor 10 or so) non-recursive version using a table instead of recursion (dynamic programming)
def traverse_terminals(expr):
input = [expr]
while input:
e = input.pop()
ops = e.operands()
if ops: # Checking ops is faster than isinstance(e, Terminal)
input.extend(ops)
else:
yield e
def traverse_unique_terminals(expr, visited=None):
input = [expr]
visited = visited or set()
while input:
e = input.pop()
if e not in visited:
visited.add(e)
ops = e.operands()
if ops:
input.extend(ops)
else:
yield e
traverse_terminals2 = traverse_unique_terminals # TODO: Replace calls with this more descriptive name
def traverse_operands(expr):
input = [expr]
while input:
e = input.pop()
if not isinstance(e, Terminal):
yield e
input.extend(e.operands())
# Moved to common because it is without dependencies and this avoids circular deps
from ufl.common import fast_pre_traversal, fast_post_traversal
def pre_traversal(expr, stack=None):
"""Yields o for each tree node o in expr, parent before child.
If a list is provided, the stack is updated while iterating."""
ufl_assert(isinstance(expr, Expr), "Expecting Expr.")
# yield parent
yield expr
# yield children
if not isinstance(expr, Terminal):
if stack is not None:
stack.append(expr)
for o in expr.operands():
for i in pre_traversal(o, stack):
yield i
if stack is not None:
stack.pop()
def post_traversal(expr, stack=None):
"""Yields o for each tree node o in expr, parent after child.
If a list is provided, the stack is updated while iterating."""
ufl_assert(isinstance(expr, Expr), "Expecting Expr.")
# yield children
if stack is not None:
stack.append(expr)
for o in expr.operands():
for i in post_traversal(o, stack):
yield i
if stack is not None:
stack.pop()
# yield parent
yield expr
def pre_walk(a, func):
"""Call func on each expression tree node in a, parent before child.
The argument a can be a Form, Integral or Expr."""
for e in iter_expressions(a):
for o in pre_traversal(e):
func(o)
def post_walk(a, func):
"""Call func on each expression tree node in a, parent after child.
The argument a can be a Form, Integral or Expr."""
for e in iter_expressions(a):
for o in post_traversal(e):
func(o)
def _walk(expr, pre_func, post_func, stack):
# visit parent on the way in
pre_func(expr, stack)
# visit children
stack.append(expr)
for o in expr.operands():
_walk(o, pre_func, post_func, stack)
stack.pop()
# visit parent on the way out
post_func(expr, stack)
def walk(a, pre_func, post_func, stack=None):
"""Call pre_func and post_func on each expression tree node in a.
The functions are called on a node before and
after its children are visited respectively.
The argument a can be a Form, Integral or Expr."""
if stack is None:
stack = []
for e in iter_expressions(a):
_walk(e, pre_func, post_func, stack)
|