ebb/src/flow_graph.erl

-module(flow_graph).

% Vertex construction
-export([hole/0, value/1, void/0, split/0, merge/0, switch/2, select/2]).
% Edge construction
-export([flow/2, func/3, index/3, range/4, tagged/3, dynamic/2, dynamic/3]).
% Graph construction
-export([singleton/1, from_list/3]).
% Graph manipulation
-export([append/2, out_edges/2]).
% Checks for validity
-export([valid_edge/1, valid_edge_list/1, valid_graph/1]).

% Use the orddict module for clarity, and the dict module for speed.
-define(DICT, orddict).

% flow_graph ::= {in    : vertex,
%                 out   : vertex,
%                 graph : dict(vertex, [edge])}
-record(flow_graph, {in, out, graph}).

% vertex ::= {ref, node}
-record(vertex, {ref, node}).

% node ::= hole | value | void | split | merge | switch | select | delayed
% value ::= term
% switch ::= {fun(A, State) -> {Tag, State}, State}
% select ::= {fun(A, State) -> {select, State} | {block, State}, State}
-record(value, {value}).
-record(switch, {switch, state}).
-record(select, {select, state}).

% edge ::= {from : vertex, to : vertex, through : link
-record(edge, {from, to, through}).

% link ::= flow | func | range | tagged | dynamic
% func ::= fun(A) -> B
% range ::= {int, int}
% tagged ::= Tag
% dyanmic ::= fun(A) -> flow_graph
-record(func, {func}).
-record(range, {from, to}).
-record(tagged, {tag}).
-record(dynamic, {code}).

%% Vertex construction
make_vertex(N) ->
    #vertex{ref=make_ref(), node=N}.

hole() ->
    make_vertex(hole).

value(X) ->
    make_vertex(#value{value=X}).

void() ->
    make_vertex(void).

split() ->
    make_vertex(split).

merge() ->
    make_vertex(merge).

switch(Switch, Init) when is_function(Switch) ->
    make_vertex(#switch{switch=Switch, state=Init}).

select(Select, Init) when is_function(Select) ->
    make_vertex(#select{select=Select, state=Init}).

delayed() ->
    make_vertex(delayed).

%% Edge construction

make_edge(From, To, Through) ->
    #edge{from=From, to=To, through=Through}.

flow(From, To) ->
    make_edge(From, To, flow).

func(From, To, Func) ->
    make_edge(From, To, #func{func=Func}).

index(From, To, N) when is_number(N) ->
    range(From, To, N, N).

range(From, To, Low, High) when is_number(Low), is_number(High), Low =< High->
    make_edge(From, To, #range{from=Low, to=High}).

tagged(From, To, Tag) ->
    make_edge(From, To, #tagged{tag=Tag}).

dynamic(From, To = #vertex{node=delayed}, Code) ->
    make_edge(From, To, #dynamic{code=Code}).

dynamic(From, Code) ->
    make_edge(From, delayed(), #dynamic{code=Code}).

%% Graph constructon

singleton(V = #vertex{}) ->
    #flow_graph{in=V, out=V, graph=orddict:store(V, [], ?DICT:new())}.

from_list(In = #vertex{}, Out = #vertex{}, Edges) ->
    FG = lists:foldl(fun(E, G) -> add_edge(G, E) end,
		     #flow_graph{in=In, out=Out, graph=?DICT:new()},
		     Edges),
    G2 = ?DICT:update(Out, fun(X)->X end, [], FG#flow_graph.graph),
    FG#flow_graph{graph=G2}.

%% Graph manipulation

append(FG1 = #flow_graph{in=In1, out=Out1},
       FG2 = #flow_graph{in=In2, out=Out2}) ->
    G = ?DICT:merge(fun(_, E1, E2) -> lists:append(E1,E2) end,
		      FG1#flow_graph.graph,
		      FG2#flow_graph.graph),
    add_edge(#flow_graph{in=In1, out=Out2, graph=G},
	     flow(Out1, In2)).

out_edges(#flow_graph{graph=G}, #vertex{ref=R}) ->
    ?DICT:find(R, G).

add_edge(FG = #flow_graph{graph=G}, E = #edge{from=From}) ->
    Add = fun(Edges) -> [E|Edges] end,
    FG#flow_graph{graph=?DICT:update(From, Add, [E], G)}.

% Checks for validity
valid_edge(#edge{from=From, to=To, through=Through}) ->
    IsNeutral = fun(flow)       -> true;
		   (#func{})    -> true;
		   (#dynamic{}) -> true;
		   (_)          -> false
		end,
    Left = case {From, Through, To} of
	       {delayed,   _,          _}        -> false;
	       {hole,      _,          _}        -> IsNeutral(Through);
	       {#value{},  _,          _}        -> IsNeutral(Through);
	       {void,      flow,       #value{}} -> true;
	       {void,      flow,       void}     -> true;
	       {void,      #dynamic{}, delayed}  -> true;
	       {void,      _,          _}        -> false;
	       {split,     #range{},   _}        -> true;
	       {split,     _,          _}        -> false;
	       {merge,     _,          _}        -> IsNeutral(Through);
	       {#switch{}, #tagged{},  _}        -> true;
	       {#switch{}, _,          _}        -> false;
	       {#select{}, _,          _}        -> IsNeutral(Through);
	       _                                 -> false
	   end,
    Right = case {From, Through, To} of
		{_,    dynamic,  delayed}   -> true;
		{_,    dynamic,  _}         -> false;
		{_,    _,        hole}      -> true;
		{void, flow,     #value{}}  -> true;
		{_,    _,        #value{}}  -> false;
		{void, flow,     void}      -> true;
		{_,    _,        void}      -> false;
		{_,    _,        split}     -> true;
		{_,    #range{}, merge}     -> true;
		{_,    _,        merge}     -> false;
		{_,    _, 	 #switch{}} -> true;
		{_,    _, 	 #select{}} -> true
	    end,
    Left and Right.

valid_edge_list(Edges) ->
    lists:all(fun valid_edge/1, Edges).

valid_graph(#flow_graph{graph=G}) ->
    lists:all(fun({_, Es}) -> valid_edge_list(Es) end,
	      ?DICT:to_list(G)).