summaryrefslogtreecommitdiff
path: root/grc/core/utils/expr_utils.py
diff options
context:
space:
mode:
authorMarcus Müller <marcus@hostalia.de>2018-09-21 00:00:57 +0200
committerMarcus Müller <marcus@hostalia.de>2018-09-21 00:00:57 +0200
commit267d669eb21c514c18a6ee979f5cf247d251f1ad (patch)
treec6120f5993f82daf13894e8bf905c4169493152e /grc/core/utils/expr_utils.py
parent896d1c9da31963ecf5b0d90942c2af51ca998a69 (diff)
parent7b20b28a9e5aa4e32ee37e89e7f80d74485344e8 (diff)
Merge branch 'merge_next' (which merges next)
This has been in the making far too long. We finally merge the next branch into master, in preparation of releasing GNU Radio 3.8. There will be breakage. There will be awesomeness. There will be progress in the greatest SDR framework to ever grace the surface of the earth. Hold tight for now.
Diffstat (limited to 'grc/core/utils/expr_utils.py')
-rw-r--r--grc/core/utils/expr_utils.py175
1 files changed, 107 insertions, 68 deletions
diff --git a/grc/core/utils/expr_utils.py b/grc/core/utils/expr_utils.py
index 2059ceff9f..427585e93c 100644
--- a/grc/core/utils/expr_utils.py
+++ b/grc/core/utils/expr_utils.py
@@ -17,18 +17,111 @@ along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
"""
+from __future__ import absolute_import, print_function
+
import string
-VAR_CHARS = string.letters + string.digits + '_'
+import six
+
+
+def expr_replace(expr, replace_dict):
+ """
+ Search for vars in the expression and add the prepend.
+
+ Args:
+ expr: an expression string
+ replace_dict: a dict of find:replace
+
+ Returns:
+ a new expression with the prepend
+ """
+ expr_splits = _expr_split(expr, var_chars=VAR_CHARS + '.')
+ for i, es in enumerate(expr_splits):
+ if es in list(replace_dict.keys()):
+ expr_splits[i] = replace_dict[es]
+ return ''.join(expr_splits)
+
+
+def get_variable_dependencies(expr, vars):
+ """
+ Return a set of variables used in this expression.
+
+ Args:
+ expr: an expression string
+ vars: a list of variable names
+
+ Returns:
+ a subset of vars used in the expression
+ """
+ expr_toks = _expr_split(expr)
+ return set(v for v in vars if v in expr_toks)
+
+
+def sort_objects(objects, get_id, get_expr):
+ """
+ Sort a list of objects according to their expressions.
+
+ Args:
+ objects: the list of objects to sort
+ get_id: the function to extract an id from the object
+ get_expr: the function to extract an expression from the object
+
+ Returns:
+ a list of sorted objects
+ """
+ id2obj = {get_id(obj): obj for obj in objects}
+ # Map obj id to expression code
+ id2expr = {get_id(obj): get_expr(obj) for obj in objects}
+ # Sort according to dependency
+ sorted_ids = _sort_variables(id2expr)
+ # Return list of sorted objects
+ return [id2obj[id] for id in sorted_ids]
+
+
+import ast
+
+
+def dependencies(expr, names=None):
+ node = ast.parse(expr, mode='eval')
+ used_ids = frozenset([n.id for n in ast.walk(node) if isinstance(n, ast.Name)])
+ return used_ids & names if names else used_ids
+
+
+def sort_objects2(objects, id_getter, expr_getter, check_circular=True):
+ known_ids = {id_getter(obj) for obj in objects}
+
+ def dependent_ids(obj):
+ deps = dependencies(expr_getter(obj))
+ return [id_ if id_ in deps else None for id_ in known_ids]
-class graph(object):
+ objects = sorted(objects, key=dependent_ids)
+
+ if check_circular: # walk var defines step by step
+ defined_ids = set() # variables defined so far
+ for obj in objects:
+ deps = dependencies(expr_getter(obj), known_ids)
+ if not defined_ids.issuperset(deps): # can't have an undefined dep
+ raise RuntimeError(obj, deps, defined_ids)
+ defined_ids.add(id_getter(obj)) # define this one
+
+ return objects
+
+
+
+
+VAR_CHARS = string.ascii_letters + string.digits + '_'
+
+
+class _graph(object):
"""
Simple graph structure held in a dictionary.
"""
- def __init__(self): self._graph = dict()
+ def __init__(self):
+ self._graph = dict()
- def __str__(self): return str(self._graph)
+ def __str__(self):
+ return str(self._graph)
def add_node(self, node_key):
if node_key in self._graph:
@@ -50,13 +143,13 @@ class graph(object):
self._graph[src_node_key].remove(dest_node_key)
def get_nodes(self):
- return self._graph.keys()
+ return list(self._graph.keys())
def get_edges(self, node_key):
return self._graph[node_key]
-def expr_split(expr, var_chars=VAR_CHARS):
+def _expr_split(expr, var_chars=VAR_CHARS):
"""
Split up an expression by non alphanumeric characters, including underscore.
Leave strings in-tact.
@@ -85,43 +178,10 @@ def expr_split(expr, var_chars=VAR_CHARS):
toks.append(char)
tok = ''
toks.append(tok)
- return filter(lambda t: t, toks)
-
-
-def expr_replace(expr, replace_dict):
- """
- Search for vars in the expression and add the prepend.
-
- Args:
- expr: an expression string
- replace_dict: a dict of find:replace
-
- Returns:
- a new expression with the prepend
- """
- expr_splits = expr_split(expr, var_chars=VAR_CHARS + '.')
- for i, es in enumerate(expr_splits):
- if es in replace_dict.keys():
- expr_splits[i] = replace_dict[es]
- return ''.join(expr_splits)
+ return [t for t in toks if t]
-def get_variable_dependencies(expr, vars):
- """
- Return a set of variables used in this expression.
-
- Args:
- expr: an expression string
- vars: a list of variable names
-
- Returns:
- a subset of vars used in the expression
- """
- expr_toks = expr_split(expr)
- return set(var for var in vars if var in expr_toks)
-
-
-def get_graph(exprs):
+def _get_graph(exprs):
"""
Get a graph representing the variable dependencies
@@ -131,19 +191,19 @@ def get_graph(exprs):
Returns:
a graph of variable deps
"""
- vars = exprs.keys()
+ vars = list(exprs.keys())
# Get dependencies for each expression, load into graph
- var_graph = graph()
+ var_graph = _graph()
for var in vars:
var_graph.add_node(var)
- for var, expr in exprs.iteritems():
+ for var, expr in six.iteritems(exprs):
for dep in get_variable_dependencies(expr, vars):
if dep != var:
var_graph.add_edge(dep, var)
return var_graph
-def sort_variables(exprs):
+def _sort_variables(exprs):
"""
Get a list of variables in order of dependencies.
@@ -154,12 +214,12 @@ def sort_variables(exprs):
a list of variable names
@throws Exception circular dependencies
"""
- var_graph = get_graph(exprs)
+ var_graph = _get_graph(exprs)
sorted_vars = list()
# Determine dependency order
while var_graph.get_nodes():
# Get a list of nodes with no edges
- indep_vars = filter(lambda var: not var_graph.get_edges(var), var_graph.get_nodes())
+ indep_vars = [var for var in var_graph.get_nodes() if not var_graph.get_edges(var)]
if not indep_vars:
raise Exception('circular dependency caught in sort_variables')
# Add the indep vars to the end of the list
@@ -168,24 +228,3 @@ def sort_variables(exprs):
for var in indep_vars:
var_graph.remove_node(var)
return reversed(sorted_vars)
-
-
-def sort_objects(objects, get_id, get_expr):
- """
- Sort a list of objects according to their expressions.
-
- Args:
- objects: the list of objects to sort
- get_id: the function to extract an id from the object
- get_expr: the function to extract an expression from the object
-
- Returns:
- a list of sorted objects
- """
- id2obj = dict([(get_id(obj), obj) for obj in objects])
- # Map obj id to expression code
- id2expr = dict([(get_id(obj), get_expr(obj)) for obj in objects])
- # Sort according to dependency
- sorted_ids = sort_variables(id2expr)
- # Return list of sorted objects
- return [id2obj[id] for id in sorted_ids]
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-03 05:46:48 +0000