%%% This file is part of RefactorErl.
%%%
%%% RefactorErl 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.
%%%
%%% RefactorErl 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 RefactorErl.  If not, see <http://plc.inf.elte.hu/erlang/>.
%%%
%%% The Original Code is RefactorErl.
%%%
%%% The Initial Developer of the Original Code is Eötvös Loránd University.
%%% Portions created  by Eötvös Loránd University and ELTE-Soft Ltd.
%%% are Copyright 2007-2025 Eötvös Loránd University, ELTE-Soft Ltd.
%%% and Ericsson Hungary. All Rights Reserved.


%%% ============================================================================
%%% Module information

%%% @doc The module implements the postdominator building algorithm.

%%% @author Istvan Bozo <bozo_i@inf.elte.hu>

-module(refsc_postdom).

-vsn("$Rev: 17551 $ ").

%% Interface functions to get the postdominator information
-export([immediate_postdominators/3]).

%% Visualization of the tree.
-export([draw_graph/1]).

-include("slicer.hrl").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Interface functions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

-spec immediate_postdominators(Form :: refsc_cfg_utils:cfg_node(),
                               CFGEdges :: [refsc_cfg_utils:cfg_edge()],
                               AppNodes :: refsc_cfg_utils:cfg_node()) ->
                                      Ret :: {[tuple()], atom()}.
%% @doc The function gets a vertex and determines the immediate
%% postominator for each vertex.
immediate_postdominators(Form, CFGEdges, Apps) ->
    Table = ets:new(temp_cfg, [bag, private]),

    FailNodes = lists:usort([ENode || {_, ENode = {error, _}, _} <- CFGEdges]),
    TempEdges = [{{ret, Form}, ?EXIT(Form), []} , {Form, {ret, Form}, []}
                 | [{ENode, ?EXIT(Form), []} || ENode <- FailNodes]],
    [ets:insert(Table, {S,E,""}) || {S,E, _} <- TempEdges],
    %% For efficiency reason, fusion of vertice selection and the
    %% table filling.
    Vertices = ordsets:from_list(
                 [?EXIT(Form) |
                  lists:append([begin
                                    ets:insert(Table, Edge),
                                    [SN, EN]
                                end || Edge = {SN, EN, _Label} <- CFGEdges])]),

    PostDominatorList = postdominators(?EXIT(Form), Vertices, Table),

    ets:delete(Table),

    Tmp = [{Vertex, ordsets:del_element(Vertex, PostDoms)}
           || {Vertex, PostDoms} <- PostDominatorList],
    VerticesExceptRoot = ordsets:del_element(?EXIT(Form), Vertices),
    ImmPostDom =
        [ begin
              PostdomsOfN = element2_o_keyfind(N, Tmp),
              VerticesToBeExtracted =
                  ordsets:union(
                    [begin
                         TempSet = element2_o_keyfind(S, Tmp),
                         ordsets:filter(fun(T) ->
                                              ordsets:is_element(T, TempSet)
                                      end, ordsets:subtract(PostdomsOfN,[S]))
                     end
                     || S <- element2_o_keyfind(N, Tmp)]),
              {N, ordsets:subtract(PostdomsOfN, VerticesToBeExtracted)}
          end
          || N <- VerticesExceptRoot],
    Type =
        case FailNodes of
            [] ->
                tree;
            _  ->
                forest
        end,
    UpdatedPostdoms =
        upd_postdom(ImmPostDom, Apps),
    {UpdatedPostdoms, Type}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Auxiliary functions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% converting into an edge syntax and updating the interrupted flow
%% edges into pottential postdom edges
upd_postdom(ImmPostDomEdges, AppNodes) ->
    UpdFun =
        fun({N, [P]}, Acc) ->
                case lists:member(N, AppNodes) of
                    true ->
                        [{N, P, potpd} | Acc];
                    false ->
                        [{N, P, pd} | Acc]
                end
        end,
    lists:foldl(UpdFun, [], ImmPostDomEdges).

%% The node `Root' is the return node of the function, the argument
%% `Vertices' is an ordered set `ordset' and the `Table' is an ets
%% table of CFG edges.
postdominators(Root, Vertices, Table) ->
    VerticesExceptRoot = ordsets:del_element(Root, Vertices),
    PostDominList = [{Root, [Root]} |
                     [ {Vertex, Vertices} || Vertex <- VerticesExceptRoot]],
    %% every iteration is performed in the given order of the
    %% VerticesExceptRoot list
    %% TODO: improve
    loop(false, Root, VerticesExceptRoot, PostDominList, Table).

loop(true,  _   , _                 , PostDominList, _Table) -> PostDominList;
loop(false, Root, VerticesExceptRoot, PostDominList, Table) ->
    Foreach =
        fun(Vertex) ->
                VertSucc  = get_succs(Table, Vertex),
                Sets      = [ordsets:add_element(Root, VerticesExceptRoot) |
                             [ element2_o_keyfind(Succ, PostDominList)
                               || Succ <- VertSucc]],
                Intersect = ordsets:intersection(Sets),
                {Vertex, ordsets:add_element(Vertex, Intersect)}
        end,
    Acc = [{Root,[Root]} | lists:map(Foreach, VerticesExceptRoot)],
    loop(Acc == PostDominList, Root, VerticesExceptRoot, Acc, Table).


get_succs(Table, Vertex) ->
    Result = ets:lookup(Table, Vertex),
    [Succ || {_Vertex, Succ, _Label} <- Result].

element2_o_keyfind(Vertex, PostDomList) ->
    case lists:keyfind(Vertex, 1, PostDomList) of
        {Vertex, PostDoms} ->
            PostDoms;
        _ ->
            throw("Something went very-very wrong!")
    end.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Drawing utility
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

draw_graph(EdgeList) ->
    refsc_utils:draw_graph(postdom, text, EdgeList).
