[Commit-gnuradio] r8986 - in grc/trunk: notes src/grc_gnuradio src/grc_gnuradio/blocks src/grc_gnuradio/data

[jblum]

Author: jblum
Date: 2008-07-23 17:32:23 -0600 (Wed, 23 Jul 2008)
New Revision: 8986

Modified:
   grc/trunk/notes/todo.txt
   grc/trunk/src/grc_gnuradio/Generator.py
   grc/trunk/src/grc_gnuradio/Param.py
   grc/trunk/src/grc_gnuradio/blocks/options.xml
   grc/trunk/src/grc_gnuradio/data/flow_graph.tmpl
   grc/trunk/src/grc_gnuradio/expr_utils.py
Log:
variable graph resolution

Modified: grc/trunk/notes/todo.txt
===================================================================
--- grc/trunk/notes/todo.txt    2008-07-23 20:33:40 UTC (rev 8985)
+++ grc/trunk/notes/todo.txt    2008-07-23 23:32:23 UTC (rev 8986)
@@ -12,16 +12,15 @@
 -command line option for additional block wrappers
 -hotkeys in action descriptions
 -log slider gui control
--variable resolution graph structure
 -recursive/nested categories
+
+############ Maybe: ####################
 -icons for certain blocks, + for add
 -zoom in/out
--hide io types
+-hide io type params
 
 ############ Problems: ####################
 -catch error on open non-existant files
--variables dependent on variables that change
--flow graph, try mouse DRAG_MOTION?
 
 ############ Suggestions: ####################
 -simple usrp

Modified: grc/trunk/src/grc_gnuradio/Generator.py
===================================================================
--- grc/trunk/src/grc_gnuradio/Generator.py     2008-07-23 20:33:40 UTC (rev 
8985)
+++ grc/trunk/src/grc_gnuradio/Generator.py     2008-07-23 23:32:23 UTC (rev 
8986)
@@ -25,6 +25,7 @@
 import sys
 import stat
 from Cheetah.Template import Template
+import expr_utils
 
 ##The default binary to execute python files.
 PYEXEC = 'python'
@@ -76,19 +77,50 @@
                Convert the flow graph to python code.
                @return a string of python code
                """
-               #load the namespace
                imports = self._flow_graph.get_imports()
                variables = self._flow_graph.get_variables()
+               #list of blocks not including variables and imports
                blocks = sorted(self._flow_graph.get_blocks(), lambda x, y: 
cmp(x.get_id(), y.get_id()))
                blocks = filter(lambda b: b not in (imports + variables) and 
b.get_enabled(), blocks)
+               #list of callbacks
+               callbacks = sum([block.get_callbacks() for block in 
self._flow_graph.get_blocks()], [])
+               #list of variable names
+               var_ids = [var.get_id() for var in variables]
+               #map var id to the expression (prepend self.)
+               var_id2expr = dict(
+                       [(var.get_id(), 
expr_utils.expr_prepend(var.get_make().split('\n')[0], var_ids, 'self.'))
+                       for var in variables]
+               )
+               #create graph structure for variables
+               variable_graph = expr_utils.get_graph(var_id2expr)
+               #map var id to direct dependents
+               #for each var id, make a list of all 2nd order edges
+               #use all edges of that id that are not also 2nd order edges
+               #meaning: list variables the ONLY depend directly on this 
variable
+               #and not variables that also depend indirectly on this variable
+               var_id2deps = dict(
+                       [(var_id, filter(lambda e: e not in 
sum([list(variable_graph.get_edges(edge))
+                               for edge in variable_graph.get_edges(var_id)], 
[]), variable_graph.get_edges(var_id)
+                               )
+                       )
+                       for var_id in var_ids]
+               )
+               #map var id to callbacks
+               var_id2cbs = dict(
+                       [(var_id, filter(lambda c: var_id in 
expr_utils.expr_split(c), callbacks))
+                       for var_id in var_ids]
+               )
+               #load the namespace
                namespace = {
                        'imports': imports,
                        'flow_graph': self._flow_graph,
                        'variables': variables,
                        'blocks': blocks,
                        'connections': self._flow_graph.get_connections(),
-                       'callbacks': sum([block.get_callbacks() for block in 
self._flow_graph.get_blocks()], []),
                        'gui_type': 
self._flow_graph.get_option('generate_options'),
+                       'var_id2expr': var_id2expr,
+                       'var_id2deps': var_id2deps,
+                       'var_id2cbs': var_id2cbs,
                }
                #build the template
                t = Template(open(FLOW_GRAPH_TEMPLATE, 'r').read(), namespace)

Modified: grc/trunk/src/grc_gnuradio/Param.py
===================================================================
--- grc/trunk/src/grc_gnuradio/Param.py 2008-07-23 20:33:40 UTC (rev 8985)
+++ grc/trunk/src/grc_gnuradio/Param.py 2008-07-23 23:32:23 UTC (rev 8986)
@@ -213,11 +213,8 @@
                code = self._to_code()
                #add self. to variables
                if self.get_parent().self_flag:
-                       code_splits = expr_utils.expr_split(code)
                        var_ids = [var.get_id() for var in 
self.get_parent().get_parent().get_variables()]
-                       for i, cs in enumerate(code_splits):
-                               if cs in var_ids: code_splits[i] = "self.%s"%cs
-                       code = ''.join(code_splits)
+                       code = expr_utils.expr_prepend(code, var_ids, 'self.')
                return code
 
        def _to_code(self):

Modified: grc/trunk/src/grc_gnuradio/blocks/options.xml
===================================================================
--- grc/trunk/src/grc_gnuradio/blocks/options.xml       2008-07-23 20:33:40 UTC 
(rev 8985)
+++ grc/trunk/src/grc_gnuradio/blocks/options.xml       2008-07-23 23:32:23 UTC 
(rev 8986)
@@ -70,7 +70,10 @@
 The window size controls the dimensions of the flow graph editor. \
 The window size (width, height) must be between (300, 300) and (2048, 2048).
 
-The generate options controls the type of code generated (wx-graphical or 
non-graphical). \
+The generate options controls the type of code generated. \
 Non-graphical flow graphs should avoid using graphical sinks or graphical 
variable controls.
+
+The id of this block determines the name of the generated file and the name of 
the class. \
+For example, an id of my_block will generate the file my_block.py and class 
my_block(gr....
        </doc>
 </block>

Modified: grc/trunk/src/grc_gnuradio/data/flow_graph.tmpl
===================================================================
--- grc/trunk/src/grc_gnuradio/data/flow_graph.tmpl     2008-07-23 20:33:40 UTC 
(rev 8985)
+++ grc/trunk/src/grc_gnuradio/data/flow_graph.tmpl     2008-07-23 23:32:23 UTC 
(rev 8986)
@@ -7,8 +7,10 @@
 address@hidden variables the variable blocks
 address@hidden blocks the signal blocks
 address@hidden connections the connections
address@hidden callbacks the block callback strings
 address@hidden gui_type the type of gui (wx gui or no gui)
address@hidden var_id2expr variable id map to expression
address@hidden var_id2deps variable id map to direct dependencies
address@hidden var_id2cbs variable id map to callback strings
 ########################################################
 #import time
 #set $DIVIDER = '#'*50
@@ -145,15 +147,17 @@
 
 ########################################################
 ##Create Callbacks
-##     Determine block callbacks that depend on the variable.
-##     Write a set method for this variable that calls the callbacks.
+##     Write a set method for this variable that calls the callbacks
+##     and sets the direct variable dependencies.
 ########################################################
 #for $var in $variables
        #set $id = $var.get_id()
-       #set $var_callbacks = filter(lambda c: id in ''.join(c.split('(')[1:]), 
$callbacks)
        def set_$(id)(self, $id):
                self.$id = $id
-       #for $callback in $var_callbacks
+       #for $dep in $var_id2deps[$id]
+               self.set_$(dep)($var_id2expr[$dep])
+       #end for
+       #for $callback in $var_id2cbs[$id]
                self.$callback
        #end for
 

Modified: grc/trunk/src/grc_gnuradio/expr_utils.py
===================================================================
--- grc/trunk/src/grc_gnuradio/expr_utils.py    2008-07-23 20:33:40 UTC (rev 
8985)
+++ grc/trunk/src/grc_gnuradio/expr_utils.py    2008-07-23 23:32:23 UTC (rev 
8986)
@@ -23,6 +23,35 @@
 import string
 VAR_CHARS = string.letters + string.digits + '_'
 
+class graph(object):
+       """!
+       Simple graph structure held in a dictionary.
+       """
+
+       def __init__(self): self._graph = dict()
+
+       def __str__(self): return str(self._graph)
+
+       def add_node(self, node_key):
+               if self._graph.has_key(node_key): return
+               self._graph[node_key] = set()
+
+       def remove_node(self, node_key):
+               if not self._graph.has_key(node_key): return
+               for edges in self._graph.values():
+                       if node_key in edges: edges.remove(node_key)
+               self._graph.pop(node_key)
+
+       def add_edge(self, src_node_key, dest_node_key):
+               self._graph[src_node_key].add(dest_node_key)
+
+       def remove_edge(self, src_node_key, dest_node_key):
+               self._graph[src_node_key].remove(dest_node_key)
+
+       def get_nodes(self): return self._graph.keys()
+
+       def get_edges(self, node_key): return self._graph[node_key]
+
 def expr_split(expr):
        """!
        Split up an expression by non alphanumeric characters, including 
underscore.
@@ -40,7 +69,7 @@
                        tok += char
                elif char in ("'", '"'):
                        toks.append(tok)
-                       tok = char 
+                       tok = char
                        quote = char
                else:
                        toks.append(tok)
@@ -49,6 +78,19 @@
        toks.append(tok)
        return filter(lambda t: t, toks)
 
+def expr_prepend(expr, vars, prepend):
+       """!
+       Search for vars in the expression and add the prepend.
+       @param expr an expression string
+       @param vars a list of variable names
+       @param prepend the prepend string
+       @return a new expression with the prepend
+       """
+       expr_splits = expr_split(expr)
+       for i, es in enumerate(expr_splits):
+               if es in vars: expr_splits[i] = prepend + es
+       return ''.join(expr_splits)
+
 def get_variable_dependencies(expr, vars):
        """!
        Return a set of variables used in this expression.
@@ -59,6 +101,21 @@
        expr_toks = expr_split(expr)
        return set(filter(lambda v: v in expr_toks, vars))
 
+def get_graph(exprs):
+       """!
+       Get a graph representing the variable dependencies
+       @param exprs a mapping of variable name to expression
+       @return a graph of variable deps
+       """
+       vars = exprs.keys()
+       #get dependencies for each expression, load into graph
+       var_graph = graph()
+       for var in vars: var_graph.add_node(var)
+       for var, expr in exprs.iteritems():
+               for dep in get_variable_dependencies(expr, vars):
+                       var_graph.add_edge(dep, var)
+       return var_graph
+
 def sort_variables(exprs):
        """!
        Get a list of variables in order of dependencies.
@@ -66,20 +123,18 @@
        @return a list of variable names
        @throws AssertionError circular dependencies
        """
-       vars = exprs.keys()
-       #get dependencies for each expression
-       vars_deps = dict([(var, get_variable_dependencies(expr, vars)) for var, 
expr in exprs.iteritems()])
+       var_graph = get_graph(exprs)
        sorted_vars = list()
        #determine dependency order
-       while vars_deps:
-               #get a list of vars with no dependencies
-               indep_vars = set(filter(lambda v: not vars_deps[v], 
vars_deps.keys()))
+       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())
                assert indep_vars
-               #remove inpep vars from dict
-               for var in indep_vars: vars_deps.pop(var)
                #add the indep vars to the end of the list
                sorted_vars.extend(sorted(indep_vars))
-               #remove deps from other vars involving indep_vars
-               for var in vars_deps.keys(): vars_deps[var] -= indep_vars
-       return sorted_vars
+               #remove each edge-less node from the graph
+               for var in indep_vars: var_graph.remove_node(var)
+       return reversed(sorted_vars)
 
+if __name__ == '__main__':
+       for i in sort_variables({'x':'1', 'y':'x+1', 'a':'x+y', 'b':'y+1', 
'c':'a+b+x+y'}): print i