15.3.321  src/lib/graph/loop-structure.api

## loop-structure.api

# Compiled by:
#     src/lib/graph/graphs.lib




# This module is responsible for locating loop structures (intervals).
# All loops have only one single entry (via the header) but
# potentially multiple exits, i.e. the header dominates all nodes
# within the loop.   Other definitions are used for ``loops'' and ``headers''
# in the literature.  We choose a structural definition that has nicer
# properties.
# 
# -- Allen Leung



###               "Long hair minimizes the need for barbers;
###                socks can be done without;
###                one leather jacket solves
###                the coat problem for many years;
###                suspenders are superfluous."
###
###                                   -- Albert Einstein


stipulate
    package odg =  oop_digraph;                                         # oop_digraph   is from   src/lib/graph/oop-digraph.pkg
    package rwv =  rw_vector;                                           # rw_vector             is from   src/lib/std/src/rw-vector.pkg
herein


    api  Loop_Structure {
        #
        package dom:  Dominator_Tree;                                   # Dominator_Tree        is from   src/lib/graph/dominator-tree.api
        package meg:  Make_Empty_Graph;                                 # Make_Empty_Graph      is from   src/lib/graph/make-empty-graph.api


        # DEF: An edge i -> j  is a backedge iff j dom i.
        #      Here, j is the header, and i -> j \in backedges (j) 
        #      A loop is identified by its header h.  

        Loop (N,E,G)                                                    # "N,E,G" stand in for types of client-package-supplied records piggybacked on our own graph, edge and node records.
            = 
            LOOP  { nesting:     Int,
                    header:      odg::Node_Id,
                    #
                    loop_nodes:  List( odg::Node_Id ),
                    backedges:   List( odg::Edge(E) ),
                    exits:       List( odg::Edge(E) )
                  };

        Loop_Info( N, E, G );

        Loop_Structure( N, E, G )
           = 
            odg::Digraph(

               Loop( N, E, G ),
               Void,
               Loop_Info ( N, E, G)
           );

        dom:             Loop_Structure (N,E,G) -> dom::Dominator_Tree (N,E,G);

        # O (n+e) 
        #
        loop_structure:  dom::Dominator_Tree(N,E,G) -> Loop_Structure(N,E,G);

        # Return an rw_vector mapping
        # node id -> nesting level:
        #
        nesting_level:  Loop_Structure (N,E,G)  ->  rwv::Rw_Vector(odg::Node_Id);

        # Return an rw_vector mapping
        # node id -> header that it
        # belongs to:
        #
        header:          Loop_Structure (N,E,G)  ->  rwv::Rw_Vector(odg::Node_Id);

        # Given a header, return the set
        # of entry edges into the loop: 
        #
        entry_edges:     Loop_Structure (N,E,G)  ->  odg::Node_Id  ->  List(odg::Edge(E));

    };    
end;


## COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.