blob: 1f288180c0298e899fbcf28ce1af036f4b118abe [file] [log] [blame]
------------------------------------------------------------------------------
-- --
-- GNAT COMPILER COMPONENTS --
-- --
-- B I N D O . G R A P H S --
-- --
-- S p e c --
-- --
-- Copyright (C) 2019-2021, Free Software Foundation, Inc. --
-- --
-- GNAT is free software; you can redistribute it and/or modify it under --
-- terms of the GNU General Public License as published by the Free Soft- --
-- ware Foundation; either version 3, or (at your option) any later ver- --
-- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --
-- for more details. You should have received a copy of the GNU General --
-- Public License distributed with GNAT; see file COPYING3. If not, go to --
-- http://www.gnu.org/licenses for a complete copy of the license. --
-- --
-- GNAT was originally developed by the GNAT team at New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc. --
-- --
------------------------------------------------------------------------------
-- For full architecture, see unit Bindo.
-- The following unit defines the various graphs used in determining the
-- elaboration order of units.
with Types; use Types;
with Bindo.Units; use Bindo.Units;
with GNAT; use GNAT;
with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables;
with GNAT.Graphs; use GNAT.Graphs;
with GNAT.Lists; use GNAT.Lists;
with GNAT.Sets; use GNAT.Sets;
package Bindo.Graphs is
---------------------------
-- Invocation graph edge --
---------------------------
-- The following type denotes an invocation graph edge handle
type Invocation_Graph_Edge_Id is new Natural;
No_Invocation_Graph_Edge : constant Invocation_Graph_Edge_Id :=
Invocation_Graph_Edge_Id'First;
First_Invocation_Graph_Edge : constant Invocation_Graph_Edge_Id :=
No_Invocation_Graph_Edge + 1;
procedure Destroy_Invocation_Graph_Edge
(Edge : in out Invocation_Graph_Edge_Id);
pragma Inline (Destroy_Invocation_Graph_Edge);
-- Destroy invocation graph edge Edge
function Hash_Invocation_Graph_Edge
(Edge : Invocation_Graph_Edge_Id) return Bucket_Range_Type;
pragma Inline (Hash_Invocation_Graph_Edge);
-- Obtain the hash value of key Edge
function Present (Edge : Invocation_Graph_Edge_Id) return Boolean;
pragma Inline (Present);
-- Determine whether invocation graph edge Edge exists
package IGE_Lists is new Doubly_Linked_Lists
(Element_Type => Invocation_Graph_Edge_Id,
"=" => "=",
Destroy_Element => Destroy_Invocation_Graph_Edge);
------------------------------
-- Invocation graph vertex --
------------------------------
-- The following type denotes an invocation graph vertex handle
type Invocation_Graph_Vertex_Id is new Natural;
No_Invocation_Graph_Vertex : constant Invocation_Graph_Vertex_Id :=
Invocation_Graph_Vertex_Id'First;
First_Invocation_Graph_Vertex : constant Invocation_Graph_Vertex_Id :=
No_Invocation_Graph_Vertex + 1;
function Hash_Invocation_Graph_Vertex
(Vertex : Invocation_Graph_Vertex_Id) return Bucket_Range_Type;
pragma Inline (Hash_Invocation_Graph_Vertex);
-- Obtain the hash value of key Vertex
function Present (Vertex : Invocation_Graph_Vertex_Id) return Boolean;
pragma Inline (Present);
-- Determine whether invocation graph vertex Vertex exists
package IGV_Sets is new Membership_Sets
(Element_Type => Invocation_Graph_Vertex_Id,
"=" => "=",
Hash => Hash_Invocation_Graph_Vertex);
-------------------------
-- Library graph cycle --
-------------------------
type Library_Graph_Cycle_Id is new Natural;
No_Library_Graph_Cycle : constant Library_Graph_Cycle_Id :=
Library_Graph_Cycle_Id'First;
First_Library_Graph_Cycle : constant Library_Graph_Cycle_Id :=
No_Library_Graph_Cycle + 1;
procedure Destroy_Library_Graph_Cycle
(Cycle : in out Library_Graph_Cycle_Id);
pragma Inline (Destroy_Library_Graph_Cycle);
-- Destroy library graph cycle Cycle
function Hash_Library_Graph_Cycle
(Cycle : Library_Graph_Cycle_Id) return Bucket_Range_Type;
pragma Inline (Hash_Library_Graph_Cycle);
-- Obtain the hash value of key Cycle
function Present (Cycle : Library_Graph_Cycle_Id) return Boolean;
pragma Inline (Present);
-- Determine whether library graph cycle Cycle exists
package LGC_Lists is new Doubly_Linked_Lists
(Element_Type => Library_Graph_Cycle_Id,
"=" => "=",
Destroy_Element => Destroy_Library_Graph_Cycle);
------------------------
-- Library graph edge --
------------------------
-- The following type denotes a library graph edge handle
type Library_Graph_Edge_Id is new Natural;
No_Library_Graph_Edge : constant Library_Graph_Edge_Id :=
Library_Graph_Edge_Id'First;
First_Library_Graph_Edge : constant Library_Graph_Edge_Id :=
No_Library_Graph_Edge + 1;
procedure Destroy_Library_Graph_Edge
(Edge : in out Library_Graph_Edge_Id);
pragma Inline (Destroy_Library_Graph_Edge);
-- Destroy library graph edge Edge
function Hash_Library_Graph_Edge
(Edge : Library_Graph_Edge_Id) return Bucket_Range_Type;
pragma Inline (Hash_Library_Graph_Edge);
-- Obtain the hash value of key Edge
function Present (Edge : Library_Graph_Edge_Id) return Boolean;
pragma Inline (Present);
-- Determine whether library graph edge Edge exists
package LGE_Lists is new Doubly_Linked_Lists
(Element_Type => Library_Graph_Edge_Id,
"=" => "=",
Destroy_Element => Destroy_Library_Graph_Edge);
package LGE_Sets is new Membership_Sets
(Element_Type => Library_Graph_Edge_Id,
"=" => "=",
Hash => Hash_Library_Graph_Edge);
--------------------------
-- Library graph vertex --
--------------------------
-- The following type denotes a library graph vertex handle
type Library_Graph_Vertex_Id is new Natural;
No_Library_Graph_Vertex : constant Library_Graph_Vertex_Id :=
Library_Graph_Vertex_Id'First;
First_Library_Graph_Vertex : constant Library_Graph_Vertex_Id :=
No_Library_Graph_Vertex + 1;
procedure Destroy_Library_Graph_Vertex
(Vertex : in out Library_Graph_Vertex_Id);
pragma Inline (Destroy_Library_Graph_Vertex);
-- Destroy library graph vertex Vertex
function Hash_Library_Graph_Vertex
(Vertex : Library_Graph_Vertex_Id) return Bucket_Range_Type;
pragma Inline (Hash_Library_Graph_Vertex);
-- Obtain the hash value of key Vertex
function Present (Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Present);
-- Determine whether library graph vertex Vertex exists
package LGV_Lists is new Doubly_Linked_Lists
(Element_Type => Library_Graph_Vertex_Id,
"=" => "=",
Destroy_Element => Destroy_Library_Graph_Vertex);
package LGV_Sets is new Membership_Sets
(Element_Type => Library_Graph_Vertex_Id,
"=" => "=",
Hash => Hash_Library_Graph_Vertex);
--------------------
-- Library_Graphs --
--------------------
package Library_Graphs is
-- The following type represents the various kinds of library graph
-- cycles. The ordering of kinds is significant, where a literal with
-- lower ordinal has a higher precedence than one with higher ordinal.
type Library_Graph_Cycle_Kind is
(Elaborate_Body_Cycle,
-- A cycle that involves at least one spec-body pair, where the
-- spec is subject to pragma Elaborate_Body. This is the highest
-- precedence cycle.
Elaborate_Cycle,
-- A cycle that involves at least one Elaborate edge
Elaborate_All_Cycle,
-- A cycle that involves at least one Elaborate_All edge
Forced_Cycle,
-- A cycle that involves at least one edge which is a byproduct of
-- the forced-elaboration-order file.
Invocation_Cycle,
-- A cycle that involves at least one invocation edge. This is the
-- lowest precedence cycle.
No_Cycle_Kind);
-- The following type represents the various kinds of library edges. The
-- order is important here, and corresponds to the order in which edges
-- are added to the graph. See Add_Edge_Kind_Check for details. If
-- changes are made such that new edge kinds are added or similar, we
-- need to make sure this type matches the code in Add_Edge_Kind_Check,
-- and Add_Edge_Kind_Check matches the order of edge adding. Likewise,
-- if the edge-adding order changes, we need consistency between this
-- enumeration type, the edge-adding order, and Add_Edge_Kind_Check.
type Library_Graph_Edge_Kind is
(Spec_Before_Body_Edge,
-- Successor denotes a body, Predecessor denotes a spec
Elaborate_Edge,
-- Successor withs Predecessor, and has pragma Elaborate for it
Elaborate_All_Edge,
-- Successor withs Predecessor, and has pragma Elaborate_All for it
With_Edge,
-- Successor withs Predecessor
Forced_Edge,
-- Successor is forced to with Predecessor by virtue of an existing
-- elaboration order provided in a file.
Invocation_Edge,
-- An invocation construct in unit Successor invokes a target in unit
-- Predecessor.
Body_Before_Spec_Edge,
-- Successor denotes spec, Predecessor denotes a body. This is a
-- special edge kind used only during the discovery of components.
-- Note that a body can never be elaborated before its spec.
No_Edge);
-----------
-- Graph --
-----------
-- The following type denotes a library graph handle. Each instance must
-- be created using routine Create.
type Library_Graph is private;
Nil : constant Library_Graph;
type LGE_Predicate_Ptr is access function
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Boolean;
type LGV_Comparator_Ptr is access function
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id;
Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind;
type LGV_Predicate_Ptr is access function
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
----------------------
-- Graph operations --
----------------------
procedure Add_Edge
(G : Library_Graph;
Pred : Library_Graph_Vertex_Id;
Succ : Library_Graph_Vertex_Id;
Kind : Library_Graph_Edge_Kind;
Activates_Task : Boolean);
pragma Inline (Add_Edge);
-- Create a new edge in library graph G with source vertex Pred and
-- destination vertex Succ. Kind denotes the nature of the edge. Flag
-- Activates_Task should be set when the edge involves task activation.
procedure Add_Vertex
(G : Library_Graph;
U_Id : Unit_Id);
pragma Inline (Add_Vertex);
-- Create a new vertex in library graph G. U_Id is the unit the vertex
-- describes.
function Create
(Initial_Vertices : Positive;
Initial_Edges : Positive) return Library_Graph;
pragma Inline (Create);
-- Create a new empty graph with vertex capacity Initial_Vertices and
-- edge capacity Initial_Edges.
procedure Destroy (G : in out Library_Graph);
pragma Inline (Destroy);
-- Destroy the contents of library graph G, rendering it unusable
procedure Find_Components (G : Library_Graph);
pragma Inline (Find_Components);
-- Find all components in library graph G
procedure Find_Cycles (G : Library_Graph);
pragma Inline (Find_Cycles);
-- Find all cycles in library graph G
function Highest_Precedence_Cycle
(G : Library_Graph) return Library_Graph_Cycle_Id;
pragma Inline (Highest_Precedence_Cycle);
-- Obtain the cycle with highest precedence among all other cycles of
-- library graph G.
function Present (G : Library_Graph) return Boolean;
pragma Inline (Present);
-- Determine whether library graph G exists
-----------------------
-- Vertex attributes --
-----------------------
function Component
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Component_Id;
pragma Inline (Component);
-- Obtain the component where vertex Vertex of library graph G resides
function Corresponding_Item
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
pragma Inline (Corresponding_Item);
-- Obtain the complementary vertex which represents the corresponding
-- spec or body of vertex Vertex of library graph G.
function Corresponding_Vertex
(G : Library_Graph;
U_Id : Unit_Id) return Library_Graph_Vertex_Id;
pragma Inline (Corresponding_Vertex);
-- Obtain the corresponding vertex of library graph G which represents
-- unit U_Id.
procedure Decrement_Pending_Predecessors
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id;
Edge : Library_Graph_Edge_Id);
pragma Inline (Decrement_Pending_Predecessors);
-- Decrease the number of pending predecessors vertex Vertex which was
-- reached via edge Edge of library graph G must wait until it can be
-- elaborated.
function File_Name
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return File_Name_Type;
pragma Inline (File_Name);
-- Obtain the name of the file where vertex Vertex of library graph G
-- resides.
function In_Elaboration_Order
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (In_Elaboration_Order);
-- Determine whether vertex Vertex of library graph G is already in some
-- elaboration order.
function Invocation_Graph_Encoding
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id)
return Invocation_Graph_Encoding_Kind;
pragma Inline (Invocation_Graph_Encoding);
-- Obtain the encoding format used to capture information related to
-- invocation vertices and edges that reside within vertex Vertex of
-- library graph G.
function Name
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Unit_Name_Type;
pragma Inline (Name);
-- Obtain the name of the unit which vertex Vertex of library graph G
-- represents.
procedure Pending_Predecessors_For_Elaboration
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id;
Strong_Preds : out Natural;
Weak_Preds : out Natural);
pragma Inline (Pending_Predecessors_For_Elaboration);
-- Obtain the number of pending strong and weak predecessors of vertex
-- Vertex of library graph G, taking into account Elaborate_Body pairs.
-- Strong predecessors are returned in Strong_Preds. Weak predecessors
-- are returned in Weak_Preds.
function Pending_Strong_Predecessors
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Natural;
pragma Inline (Pending_Strong_Predecessors);
-- Obtain the number of pending strong predecessors vertex Vertex of
-- library graph G must wait on until it can be elaborated.
function Pending_Weak_Predecessors
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Natural;
pragma Inline (Pending_Weak_Predecessors);
-- Obtain the number of pending weak predecessors vertex Vertex of
-- library graph G must wait on until it can be elaborated.
procedure Set_Corresponding_Item
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id;
Val : Library_Graph_Vertex_Id);
pragma Inline (Set_Corresponding_Item);
-- Set the complementary vertex which represents the corresponding
-- spec or body of vertex Vertex of library graph G to value Val.
procedure Set_In_Elaboration_Order
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id;
Val : Boolean := True);
pragma Inline (Set_In_Elaboration_Order);
-- Mark vertex Vertex of library graph G as included in some elaboration
-- order depending on value Val.
function Unit
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Unit_Id;
pragma Inline (Unit);
-- Obtain the unit vertex Vertex of library graph G represents
---------------------
-- Edge attributes --
---------------------
function Activates_Task
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Boolean;
pragma Inline (Activates_Task);
-- Determine whether edge Edge of library graph G activates a task
function Kind
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Library_Graph_Edge_Kind;
pragma Inline (Kind);
-- Obtain the nature of edge Edge of library graph G
function Predecessor
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Library_Graph_Vertex_Id;
pragma Inline (Predecessor);
-- Obtain the predecessor vertex of edge Edge of library graph G
function Successor
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Library_Graph_Vertex_Id;
pragma Inline (Successor);
-- Obtain the successor vertex of edge Edge of library graph G
--------------------------
-- Component attributes --
--------------------------
procedure Decrement_Pending_Predecessors
(G : Library_Graph;
Comp : Component_Id;
Edge : Library_Graph_Edge_Id);
pragma Inline (Decrement_Pending_Predecessors);
-- Decrease the number of pending predecessors component Comp which was
-- reached via edge Edge of library graph G must wait on until it can be
-- elaborated.
function Pending_Strong_Predecessors
(G : Library_Graph;
Comp : Component_Id) return Natural;
pragma Inline (Pending_Strong_Predecessors);
-- Obtain the number of pending strong predecessors component Comp of
-- library graph G must wait on until it can be elaborated.
function Pending_Weak_Predecessors
(G : Library_Graph;
Comp : Component_Id) return Natural;
pragma Inline (Pending_Weak_Predecessors);
-- Obtain the number of pending weak predecessors component Comp of
-- library graph G must wait on until it can be elaborated.
----------------------
-- Cycle attributes --
----------------------
function Invocation_Edge_Count
(G : Library_Graph;
Cycle : Library_Graph_Cycle_Id) return Natural;
pragma Inline (Invocation_Edge_Count);
-- Obtain the number of invocation edges in cycle Cycle of library
-- graph G.
function Kind
(G : Library_Graph;
Cycle : Library_Graph_Cycle_Id) return Library_Graph_Cycle_Kind;
pragma Inline (Kind);
-- Obtain the nature of cycle Cycle of library graph G
function Length
(G : Library_Graph;
Cycle : Library_Graph_Cycle_Id) return Natural;
pragma Inline (Length);
-- Obtain the length of cycle Cycle of library graph G
---------------
-- Semantics --
---------------
function Complementary_Vertex
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id;
Force_Complement : Boolean) return Library_Graph_Vertex_Id;
pragma Inline (Complementary_Vertex);
-- Obtain the complementary vertex of vertex Vertex of library graph G
-- as follows:
--
-- * If Vertex is the spec of an Elaborate_Body pair, return the body
-- * If Vertex is the body of an Elaborate_Body pair, return the spec
--
-- This behavior can be forced by setting flag Force_Complement to True.
function Contains_Elaborate_All_Edge
(G : Library_Graph;
Cycle : Library_Graph_Cycle_Id) return Boolean;
pragma Inline (Contains_Elaborate_All_Edge);
-- Determine whether cycle Cycle of library graph G contains an
-- Elaborate_All edge.
function Contains_Static_Successor_Edge
(G : Library_Graph;
Cycle : Library_Graph_Cycle_Id) return Boolean;
pragma Inline (Contains_Static_Successor_Edge);
-- Determine whether cycle Cycle of library graph G contains an edge
-- where the successor was compiled using the static model.
function Contains_Task_Activation
(G : Library_Graph;
Cycle : Library_Graph_Cycle_Id) return Boolean;
pragma Inline (Contains_Task_Activation);
-- Determine whether cycle Cycle of library graph G contains an
-- invocation edge where the path it represents involves a task
-- activation.
function Has_Elaborate_All_Cycle (G : Library_Graph) return Boolean;
pragma Inline (Has_Elaborate_All_Cycle);
-- Determine whether library graph G contains a cycle involving pragma
-- Elaborate_All.
function Has_No_Elaboration_Code
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Has_No_Elaboration_Code);
-- Determine whether vertex Vertex of library graph G represents a unit
-- that lacks elaboration code.
function In_Same_Component
(G : Library_Graph;
Left : Library_Graph_Vertex_Id;
Right : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (In_Same_Component);
-- Determine whether vertices Left and Right of library graph G reside
-- in the same component.
function Is_Body
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Body);
-- Determine whether vertex Vertex of library graph G denotes a body
function Is_Body_Of_Spec_With_Elaborate_Body
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Body_Of_Spec_With_Elaborate_Body);
-- Determine whether vertex Vertex of library graph G denotes a body
-- with a corresponding spec, and the spec has pragma Elaborate_Body.
function Is_Body_With_Spec
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Body_With_Spec);
-- Determine whether vertex Vertex of library graph G denotes a body
-- with a corresponding spec.
function Is_Dynamically_Elaborated
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Dynamically_Elaborated);
-- Determine whether vertex Vertex of library graph G was compiled
-- using the dynamic model.
function Is_Elaborable_Component
(G : Library_Graph;
Comp : Component_Id) return Boolean;
pragma Inline (Is_Elaborable_Component);
-- Determine whether component Comp of library graph G is not waiting on
-- any predecessors, and can thus be elaborated.
function Is_Elaborable_Vertex
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Elaborable_Vertex);
-- Determine whether vertex Vertex of library graph G is not waiting on
-- any predecessors, and can thus be elaborated.
function Is_Elaborate_All_Edge
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Boolean;
pragma Inline (Is_Elaborate_All_Edge);
-- Determine whether edge Edge of library graph G is an edge whose
-- predecessor is subject to pragma Elaborate_All.
function Is_Elaborate_Body_Edge
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Boolean;
pragma Inline (Is_Elaborate_Body_Edge);
-- Determine whether edge Edge of library graph G has a successor
-- that is either a spec subject to pragma Elaborate_Body, or a body
-- that completes such a spec.
function Is_Elaborate_Edge
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Boolean;
pragma Inline (Is_Elaborate_Edge);
-- Determine whether edge Edge of library graph G is an edge whose
-- predecessor is subject to pragma Elaborate.
function Is_Elaborate_Body_Pair
(G : Library_Graph;
Spec_Vertex : Library_Graph_Vertex_Id;
Body_Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Elaborate_Body_Pair);
-- Determine whether vertices Spec_Vertex and Body_Vertex of library
-- graph G denote a spec subject to Elaborate_Body and its completing
-- body.
function Is_Forced_Edge
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Boolean;
pragma Inline (Is_Forced_Edge);
-- Determine whether edge Edge of library graph G is a byproduct of the
-- forced-elaboration-order file.
function Is_Internal_Unit
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Internal_Unit);
-- Determine whether vertex Vertex of library graph G denotes an
-- internal unit.
function Is_Invocation_Edge
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Boolean;
pragma Inline (Is_Invocation_Edge);
-- Determine whether edge Edge of library graph G came from the
-- traversal of the invocation graph.
function Is_Predefined_Unit
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Predefined_Unit);
-- Determine whether vertex Vertex of library graph G denotes a
-- predefined unit.
function Is_Preelaborated_Unit
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Preelaborated_Unit);
-- Determine whether vertex Vertex of library graph G denotes a unit
-- subject to pragma Pure or Preelaborable.
function Is_Spec
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Spec);
-- Determine whether vertex Vertex of library graph G denotes a spec
function Is_Spec_Before_Body_Edge
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Boolean;
pragma Inline (Is_Spec_Before_Body_Edge);
-- Determine whether edge Edge of library graph G links a predecessor
-- spec and a successor body belonging to the same unit.
function Is_Spec_With_Body
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Spec_With_Body);
-- Determine whether vertex Vertex of library graph G denotes a spec
-- with a corresponding body.
function Is_Spec_With_Elaborate_Body
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Spec_With_Elaborate_Body);
-- Determine whether vertex Vertex of library graph G denotes a spec
-- with a corresponding body, and is subject to pragma Elaborate_Body.
function Is_Weakly_Elaborable_Vertex
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Is_Weakly_Elaborable_Vertex);
-- Determine whether vertex Vertex of library graph G is waiting on
-- weak predecessors only, in which case it can be elaborated assuming
-- that the weak edges will not be exercised at elaboration time.
function Is_With_Edge
(G : Library_Graph;
Edge : Library_Graph_Edge_Id) return Boolean;
pragma Inline (Is_With_Edge);
-- Determine whether edge Edge of library graph G is the result of a
-- with dependency between its successor and predecessor.
function Needs_Elaboration
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Boolean;
pragma Inline (Needs_Elaboration);
-- Determine whether vertex Vertex of library graph G represents a unit
-- that needs to be elaborated.
function Proper_Body
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
pragma Inline (Proper_Body);
-- Obtain the body of vertex Vertex of library graph G
function Proper_Spec
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
pragma Inline (Proper_Spec);
-- Obtain the spec of vertex Vertex of library graph G
----------------
-- Statistics --
----------------
function Library_Graph_Edge_Count
(G : Library_Graph;
Kind : Library_Graph_Edge_Kind) return Natural;
pragma Inline (Library_Graph_Edge_Count);
-- Obtain the total number of edges of kind Kind in library graph G
function Number_Of_Component_Vertices
(G : Library_Graph;
Comp : Component_Id) return Natural;
pragma Inline (Number_Of_Component_Vertices);
-- Obtain the total number of vertices component Comp of library graph
-- contains.
function Number_Of_Components (G : Library_Graph) return Natural;
pragma Inline (Number_Of_Components);
-- Obtain the total number of components in library graph G
function Number_Of_Cycles (G : Library_Graph) return Natural;
pragma Inline (Number_Of_Cycles);
-- Obtain the total number of cycles in library graph G
function Number_Of_Edges (G : Library_Graph) return Natural;
pragma Inline (Number_Of_Edges);
-- Obtain the total number of edges in library graph G
function Number_Of_Edges_To_Successors
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Natural;
pragma Inline (Number_Of_Edges_To_Successors);
-- Obtain the total number of edges to successors vertex Vertex of
-- library graph G has.
function Number_Of_Vertices (G : Library_Graph) return Natural;
pragma Inline (Number_Of_Vertices);
-- Obtain the total number of vertices in library graph G
---------------
-- Iterators --
---------------
-- The following type represents an iterator over all cycles of a
-- library graph.
type All_Cycle_Iterator is private;
function Has_Next (Iter : All_Cycle_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more cycles to examine
function Iterate_All_Cycles
(G : Library_Graph) return All_Cycle_Iterator;
pragma Inline (Iterate_All_Cycles);
-- Obtain an iterator over all cycles of library graph G
procedure Next
(Iter : in out All_Cycle_Iterator;
Cycle : out Library_Graph_Cycle_Id);
pragma Inline (Next);
-- Return the current cycle referenced by iterator Iter and advance to
-- the next available cycle.
-- The following type represents an iterator over all edges of a library
-- graph.
type All_Edge_Iterator is private;
function Has_Next (Iter : All_Edge_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more edges to examine
function Iterate_All_Edges (G : Library_Graph) return All_Edge_Iterator;
pragma Inline (Iterate_All_Edges);
-- Obtain an iterator over all edges of library graph G
procedure Next
(Iter : in out All_Edge_Iterator;
Edge : out Library_Graph_Edge_Id);
pragma Inline (Next);
-- Return the current edge referenced by iterator Iter and advance to
-- the next available edge.
-- The following type represents an iterator over all vertices of a
-- library graph.
type All_Vertex_Iterator is private;
function Has_Next (Iter : All_Vertex_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more vertices to examine
function Iterate_All_Vertices
(G : Library_Graph) return All_Vertex_Iterator;
pragma Inline (Iterate_All_Vertices);
-- Obtain an iterator over all vertices of library graph G
procedure Next
(Iter : in out All_Vertex_Iterator;
Vertex : out Library_Graph_Vertex_Id);
pragma Inline (Next);
-- Return the current vertex referenced by iterator Iter and advance
-- to the next available vertex.
-- The following type represents an iterator over all components of a
-- library graph.
type Component_Iterator is private;
function Has_Next (Iter : Component_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more components to examine
function Iterate_Components
(G : Library_Graph) return Component_Iterator;
pragma Inline (Iterate_Components);
-- Obtain an iterator over all components of library graph G
procedure Next
(Iter : in out Component_Iterator;
Comp : out Component_Id);
pragma Inline (Next);
-- Return the current component referenced by iterator Iter and advance
-- to the next available component.
-- The following type represents an iterator over all vertices of a
-- component.
type Component_Vertex_Iterator is private;
function Has_Next (Iter : Component_Vertex_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more vertices to examine
function Iterate_Component_Vertices
(G : Library_Graph;
Comp : Component_Id) return Component_Vertex_Iterator;
pragma Inline (Iterate_Component_Vertices);
-- Obtain an iterator over all vertices of component Comp of library
-- graph G.
procedure Next
(Iter : in out Component_Vertex_Iterator;
Vertex : out Library_Graph_Vertex_Id);
pragma Inline (Next);
-- Return the current vertex referenced by iterator Iter and advance
-- to the next available vertex.
-- The following type represents an iterator over all edges that form a
-- cycle.
type Edges_Of_Cycle_Iterator is private;
function Has_Next (Iter : Edges_Of_Cycle_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more edges to examine
function Iterate_Edges_Of_Cycle
(G : Library_Graph;
Cycle : Library_Graph_Cycle_Id) return Edges_Of_Cycle_Iterator;
pragma Inline (Iterate_Edges_Of_Cycle);
-- Obtain an iterator over all edges that form cycle Cycle of library
-- graph G.
procedure Next
(Iter : in out Edges_Of_Cycle_Iterator;
Edge : out Library_Graph_Edge_Id);
pragma Inline (Next);
-- Return the current edge referenced by iterator Iter and advance to
-- the next available edge.
-- The following type represents an iterator over all edges that reach
-- successors starting from a particular predecessor vertex.
type Edges_To_Successors_Iterator is private;
function Has_Next (Iter : Edges_To_Successors_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more edges to examine
function Iterate_Edges_To_Successors
(G : Library_Graph;
Vertex : Library_Graph_Vertex_Id) return Edges_To_Successors_Iterator;
pragma Inline (Iterate_Edges_To_Successors);
-- Obtain an iterator over all edges to successors with predecessor
-- vertex Vertex of library graph G.
procedure Next
(Iter : in out Edges_To_Successors_Iterator;
Edge : out Library_Graph_Edge_Id);
pragma Inline (Next);
-- Return the current edge referenced by iterator Iter and advance to
-- the next available edge.
private
--------------
-- Vertices --
--------------
-- The following type represents the attributes of a library graph
-- vertex.
type Library_Graph_Vertex_Attributes is record
Corresponding_Item : Library_Graph_Vertex_Id :=
No_Library_Graph_Vertex;
-- The reference to the corresponding spec or body. This attribute is
-- set as follows:
--
-- * If predicate Is_Body_With_Spec is True, the reference denotes
-- the corresponding spec.
--
-- * If predicate Is_Spec_With_Body is True, the reference denotes
-- the corresponding body.
--
-- * Otherwise the attribute remains empty.
In_Elaboration_Order : Boolean := False;
-- Set when this vertex is elaborated
Pending_Strong_Predecessors : Natural := 0;
-- The number of pending strong predecessor vertices this vertex must
-- wait on before it can be elaborated.
Pending_Weak_Predecessors : Natural := 0;
-- The number of weak predecessor vertices this vertex must wait on
-- before it can be elaborated.
Unit : Unit_Id := No_Unit_Id;
-- The reference to unit this vertex represents
end record;
No_Library_Graph_Vertex_Attributes :
constant Library_Graph_Vertex_Attributes :=
(Corresponding_Item => No_Library_Graph_Vertex,
In_Elaboration_Order => False,
Pending_Strong_Predecessors => 0,
Pending_Weak_Predecessors => 0,
Unit => No_Unit_Id);
procedure Destroy_Library_Graph_Vertex_Attributes
(Attrs : in out Library_Graph_Vertex_Attributes);
pragma Inline (Destroy_Library_Graph_Vertex_Attributes);
-- Destroy the contents of attributes Attrs
package LGV_Tables is new Dynamic_Hash_Tables
(Key_Type => Library_Graph_Vertex_Id,
Value_Type => Library_Graph_Vertex_Attributes,
No_Value => No_Library_Graph_Vertex_Attributes,
Expansion_Threshold => 1.5,
Expansion_Factor => 2,
Compression_Threshold => 0.3,
Compression_Factor => 2,
"=" => "=",
Destroy_Value => Destroy_Library_Graph_Vertex_Attributes,
Hash => Hash_Library_Graph_Vertex);
-----------
-- Edges --
-----------
-- The following type represents the attributes of a library graph edge
type Library_Graph_Edge_Attributes is record
Activates_Task : Boolean := False;
-- Set for an invocation edge, where at least one of the paths the
-- edge represents activates a task.
Kind : Library_Graph_Edge_Kind := No_Edge;
-- The nature of the library graph edge
end record;
No_Library_Graph_Edge_Attributes :
constant Library_Graph_Edge_Attributes :=
(Activates_Task => False,
Kind => No_Edge);
procedure Destroy_Library_Graph_Edge_Attributes
(Attrs : in out Library_Graph_Edge_Attributes);
pragma Inline (Destroy_Library_Graph_Edge_Attributes);
-- Destroy the contents of attributes Attrs
package LGE_Tables is new Dynamic_Hash_Tables
(Key_Type => Library_Graph_Edge_Id,
Value_Type => Library_Graph_Edge_Attributes,
No_Value => No_Library_Graph_Edge_Attributes,
Expansion_Threshold => 1.5,
Expansion_Factor => 2,
Compression_Threshold => 0.3,
Compression_Factor => 2,
"=" => "=",
Destroy_Value => Destroy_Library_Graph_Edge_Attributes,
Hash => Hash_Library_Graph_Edge);
----------------
-- Components --
----------------
-- The following type represents the attributes of a component
type Component_Attributes is record
Pending_Strong_Predecessors : Natural := 0;
-- The number of pending strong predecessor components this component
-- must wait on before it can be elaborated.
Pending_Weak_Predecessors : Natural := 0;
-- The number of pending weak predecessor components this component
-- must wait on before it can be elaborated.
end record;
No_Component_Attributes : constant Component_Attributes :=
(Pending_Strong_Predecessors => 0,
Pending_Weak_Predecessors => 0);
procedure Destroy_Component_Attributes
(Attrs : in out Component_Attributes);
pragma Inline (Destroy_Component_Attributes);
-- Destroy the contents of attributes Attrs
package Component_Tables is new Dynamic_Hash_Tables
(Key_Type => Component_Id,
Value_Type => Component_Attributes,
No_Value => No_Component_Attributes,
Expansion_Threshold => 1.5,
Expansion_Factor => 2,
Compression_Threshold => 0.3,
Compression_Factor => 2,
"=" => "=",
Destroy_Value => Destroy_Component_Attributes,
Hash => Hash_Component);
------------
-- Cycles --
------------
-- The following type represents the attributes of a cycle
type Library_Graph_Cycle_Attributes is record
Invocation_Edge_Count : Natural := 0;
-- The number of invocation edges within the cycle
Kind : Library_Graph_Cycle_Kind := No_Cycle_Kind;
-- The nature of the cycle
Path : LGE_Lists.Doubly_Linked_List := LGE_Lists.Nil;
-- The path of edges that form the cycle
end record;
No_Library_Graph_Cycle_Attributes :
constant Library_Graph_Cycle_Attributes :=
(Invocation_Edge_Count => 0,
Kind => No_Cycle_Kind,
Path => LGE_Lists.Nil);
procedure Destroy_Library_Graph_Cycle_Attributes
(Attrs : in out Library_Graph_Cycle_Attributes);
pragma Inline (Destroy_Library_Graph_Cycle_Attributes);
-- Destroy the contents of attributes Attrs
function Hash_Library_Graph_Cycle_Attributes
(Attrs : Library_Graph_Cycle_Attributes) return Bucket_Range_Type;
pragma Inline (Hash_Library_Graph_Cycle_Attributes);
-- Obtain the hash of key Attrs
function Same_Library_Graph_Cycle_Attributes
(Left : Library_Graph_Cycle_Attributes;
Right : Library_Graph_Cycle_Attributes) return Boolean;
pragma Inline (Same_Library_Graph_Cycle_Attributes);
-- Determine whether cycle attributes Left and Right are the same
package LGC_Tables is new Dynamic_Hash_Tables
(Key_Type => Library_Graph_Cycle_Id,
Value_Type => Library_Graph_Cycle_Attributes,
No_Value => No_Library_Graph_Cycle_Attributes,
Expansion_Threshold => 1.5,
Expansion_Factor => 2,
Compression_Threshold => 0.3,
Compression_Factor => 2,
"=" => "=",
Destroy_Value => Destroy_Library_Graph_Cycle_Attributes,
Hash => Hash_Library_Graph_Cycle);
--------------------
-- Recorded edges --
--------------------
-- The following type represents a relation between a predecessor and
-- successor vertices.
type Predecessor_Successor_Relation is record
Predecessor : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
-- The source vertex
Successor : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
-- The destination vertex
end record;
No_Predecessor_Successor_Relation :
constant Predecessor_Successor_Relation :=
(Predecessor => No_Library_Graph_Vertex,
Successor => No_Library_Graph_Vertex);
function Hash_Predecessor_Successor_Relation
(Rel : Predecessor_Successor_Relation) return Bucket_Range_Type;
pragma Inline (Hash_Predecessor_Successor_Relation);
-- Obtain the hash value of key Rel
package RE_Sets is new Membership_Sets
(Element_Type => Predecessor_Successor_Relation,
"=" => "=",
Hash => Hash_Predecessor_Successor_Relation);
----------------
-- Statistics --
----------------
type Library_Graph_Edge_Counts is
array (Library_Graph_Edge_Kind) of Natural;
-----------
-- Units --
-----------
package Unit_Tables is new Dynamic_Hash_Tables
(Key_Type => Unit_Id,
Value_Type => Library_Graph_Vertex_Id,
No_Value => No_Library_Graph_Vertex,
Expansion_Threshold => 1.5,
Expansion_Factor => 2,
Compression_Threshold => 0.3,
Compression_Factor => 2,
"=" => "=",
Destroy_Value => Destroy_Library_Graph_Vertex,
Hash => Hash_Unit);
-----------
-- Graph --
-----------
package DG is new Directed_Graphs
(Vertex_Id => Library_Graph_Vertex_Id,
No_Vertex => No_Library_Graph_Vertex,
Hash_Vertex => Hash_Library_Graph_Vertex,
Same_Vertex => "=",
Edge_Id => Library_Graph_Edge_Id,
No_Edge => No_Library_Graph_Edge,
Hash_Edge => Hash_Library_Graph_Edge,
Same_Edge => "=");
-- The following type represents the attributes of a library graph
type Library_Graph_Attributes is record
Component_Attributes : Component_Tables.Dynamic_Hash_Table :=
Component_Tables.Nil;
-- The map of component -> component attributes for all components in
-- the graph.
Counts : Library_Graph_Edge_Counts := (others => 0);
-- Edge statistics
Cycle_Attributes : LGC_Tables.Dynamic_Hash_Table := LGC_Tables.Nil;
-- The map of cycle -> cycle attributes for all cycles in the graph
Cycles : LGC_Lists.Doubly_Linked_List := LGC_Lists.Nil;
-- The list of all cycles in the graph, sorted based on precedence
Edge_Attributes : LGE_Tables.Dynamic_Hash_Table := LGE_Tables.Nil;
-- The map of edge -> edge attributes for all edges in the graph
Graph : DG.Directed_Graph := DG.Nil;
-- The underlying graph describing the relations between edges and
-- vertices.
Recorded_Edges : RE_Sets.Membership_Set := RE_Sets.Nil;
-- The set of recorded edges, used to prevent duplicate edges in the
-- graph.
Unit_To_Vertex : Unit_Tables.Dynamic_Hash_Table := Unit_Tables.Nil;
-- The map of unit -> vertex
Vertex_Attributes : LGV_Tables.Dynamic_Hash_Table := LGV_Tables.Nil;
-- The map of vertex -> vertex attributes for all vertices in the
-- graph.
end record;
type Library_Graph is access Library_Graph_Attributes;
Nil : constant Library_Graph := null;
---------------
-- Iterators --
---------------
type All_Cycle_Iterator is new LGC_Lists.Iterator;
type All_Edge_Iterator is new DG.All_Edge_Iterator;
type All_Vertex_Iterator is new DG.All_Vertex_Iterator;
type Component_Iterator is new DG.Component_Iterator;
type Component_Vertex_Iterator is new DG.Component_Vertex_Iterator;
type Edges_Of_Cycle_Iterator is new LGE_Lists.Iterator;
type Edges_To_Successors_Iterator is new DG.Outgoing_Edge_Iterator;
end Library_Graphs;
-----------------------
-- Invocation_Graphs --
-----------------------
package Invocation_Graphs is
-----------
-- Graph --
-----------
-- The following type denotes an invocation graph handle. Each instance
-- must be created using routine Create.
type Invocation_Graph is private;
Nil : constant Invocation_Graph;
----------------------
-- Graph operations --
----------------------
procedure Add_Edge
(G : Invocation_Graph;
Source : Invocation_Graph_Vertex_Id;
Target : Invocation_Graph_Vertex_Id;
IR_Id : Invocation_Relation_Id);
pragma Inline (Add_Edge);
-- Create a new edge in invocation graph G with source vertex Source and
-- destination vertex Target. IR_Id is the invocation relation the edge
-- describes.
procedure Add_Vertex
(G : Invocation_Graph;
IC_Id : Invocation_Construct_Id;
Body_Vertex : Library_Graph_Vertex_Id;
Spec_Vertex : Library_Graph_Vertex_Id);
pragma Inline (Add_Vertex);
-- Create a new vertex in invocation graph G. IC_Id is the invocation
-- construct the vertex describes. Body_Vertex denotes the library graph
-- vertex where the invocation construct's body is declared. Spec_Vertex
-- is the library graph vertex where the invocation construct's spec is
-- declared.
function Create
(Initial_Vertices : Positive;
Initial_Edges : Positive;
Lib_Graph : Library_Graphs.Library_Graph)
return Invocation_Graph;
pragma Inline (Create);
-- Create a new empty graph with vertex capacity Initial_Vertices
-- and edge capacity Initial_Edges. Lib_Graph is the library graph
-- corresponding to this invocation graph.
function Get_Lib_Graph
(G : Invocation_Graph) return Library_Graphs.Library_Graph;
pragma Inline (Get_Lib_Graph);
-- Return the library graph corresponding to this invocation graph
procedure Destroy (G : in out Invocation_Graph);
pragma Inline (Destroy);
-- Destroy the contents of invocation graph G, rendering it unusable
function Present (G : Invocation_Graph) return Boolean;
pragma Inline (Present);
-- Determine whether invocation graph G exists
-----------------------
-- Vertex attributes --
-----------------------
function Body_Vertex
(G : Invocation_Graph;
Vertex : Invocation_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
pragma Inline (Body_Vertex);
-- Obtain the library graph vertex where the body of the invocation
-- construct represented by vertex Vertex of invocation graph G is
-- declared.
function Column
(G : Invocation_Graph;
Vertex : Invocation_Graph_Vertex_Id) return Nat;
pragma Inline (Column);
-- Obtain the column number where the invocation construct vertex Vertex
-- of invocation graph G describes.
function Construct
(G : Invocation_Graph;
Vertex : Invocation_Graph_Vertex_Id) return Invocation_Construct_Id;
pragma Inline (Construct);
-- Obtain the invocation construct vertex Vertex of invocation graph G
-- describes.
function Corresponding_Vertex
(G : Invocation_Graph;
IS_Id : Invocation_Signature_Id) return Invocation_Graph_Vertex_Id;
pragma Inline (Corresponding_Vertex);
-- Obtain the vertex of invocation graph G that corresponds to signature
-- IS_Id.
function Line
(G : Invocation_Graph;
Vertex : Invocation_Graph_Vertex_Id) return Nat;
pragma Inline (Line);
-- Obtain the line number where the invocation construct vertex Vertex
-- of invocation graph G describes.
function Name
(G : Invocation_Graph;
Vertex : Invocation_Graph_Vertex_Id) return Name_Id;
pragma Inline (Name);
-- Obtain the name of the construct vertex Vertex of invocation graph G
-- describes.
function Spec_Vertex
(G : Invocation_Graph;
Vertex : Invocation_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
pragma Inline (Spec_Vertex);
-- Obtain the library graph vertex where the spec of the invocation
-- construct represented by vertex Vertex of invocation graph G is
-- declared.
---------------------
-- Edge attributes --
---------------------
function Extra
(G : Invocation_Graph;
Edge : Invocation_Graph_Edge_Id) return Name_Id;
pragma Inline (Extra);
-- Obtain the extra name used in error diagnostics of edge Edge of
-- invocation graph G.
function Kind
(G : Invocation_Graph;
Edge : Invocation_Graph_Edge_Id) return Invocation_Kind;
pragma Inline (Kind);
-- Obtain the nature of edge Edge of invocation graph G
function Relation
(G : Invocation_Graph;
Edge : Invocation_Graph_Edge_Id) return Invocation_Relation_Id;
pragma Inline (Relation);
-- Obtain the relation edge Edge of invocation graph G describes
function Target
(G : Invocation_Graph;
Edge : Invocation_Graph_Edge_Id) return Invocation_Graph_Vertex_Id;
pragma Inline (Target);
-- Obtain the target vertex edge Edge of invocation graph G designates
----------------
-- Statistics --
----------------
function Invocation_Graph_Edge_Count
(G : Invocation_Graph;
Kind : Invocation_Kind) return Natural;
pragma Inline (Invocation_Graph_Edge_Count);
-- Obtain the total number of edges of kind Kind in invocation graph G
function Number_Of_Edges (G : Invocation_Graph) return Natural;
pragma Inline (Number_Of_Edges);
-- Obtain the total number of edges in invocation graph G
function Number_Of_Edges_To_Targets
(G : Invocation_Graph;
Vertex : Invocation_Graph_Vertex_Id) return Natural;
pragma Inline (Number_Of_Edges_To_Targets);
-- Obtain the total number of edges to targets vertex Vertex of
-- invocation graph G has.
function Number_Of_Elaboration_Roots
(G : Invocation_Graph) return Natural;
pragma Inline (Number_Of_Elaboration_Roots);
-- Obtain the total number of elaboration roots in invocation graph G
function Number_Of_Vertices (G : Invocation_Graph) return Natural;
pragma Inline (Number_Of_Vertices);
-- Obtain the total number of vertices in invocation graph G
---------------
-- Iterators --
---------------
-- The following type represents an iterator over all edges of an
-- invocation graph.
type All_Edge_Iterator is private;
function Has_Next (Iter : All_Edge_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more edges to examine
function Iterate_All_Edges
(G : Invocation_Graph) return All_Edge_Iterator;
pragma Inline (Iterate_All_Edges);
-- Obtain an iterator over all edges of invocation graph G
procedure Next
(Iter : in out All_Edge_Iterator;
Edge : out Invocation_Graph_Edge_Id);
pragma Inline (Next);
-- Return the current edge referenced by iterator Iter and advance to
-- the next available edge.
-- The following type represents an iterator over all vertices of an
-- invocation graph.
type All_Vertex_Iterator is private;
function Has_Next (Iter : All_Vertex_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more vertices to examine
function Iterate_All_Vertices
(G : Invocation_Graph) return All_Vertex_Iterator;
pragma Inline (Iterate_All_Vertices);
-- Obtain an iterator over all vertices of invocation graph G
procedure Next
(Iter : in out All_Vertex_Iterator;
Vertex : out Invocation_Graph_Vertex_Id);
pragma Inline (Next);
-- Return the current vertex referenced by iterator Iter and advance
-- to the next available vertex.
-- The following type represents an iterator over all edges that reach
-- targets starting from a particular source vertex.
type Edges_To_Targets_Iterator is private;
function Has_Next (Iter : Edges_To_Targets_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more edges to examine
function Iterate_Edges_To_Targets
(G : Invocation_Graph;
Vertex : Invocation_Graph_Vertex_Id) return Edges_To_Targets_Iterator;
pragma Inline (Iterate_Edges_To_Targets);
-- Obtain an iterator over all edges to targets with source vertex
-- Vertex of invocation graph G.
procedure Next
(Iter : in out Edges_To_Targets_Iterator;
Edge : out Invocation_Graph_Edge_Id);
pragma Inline (Next);
-- Return the current edge referenced by iterator Iter and advance to
-- the next available edge.
-- The following type represents an iterator over all vertices of an
-- invocation graph that denote the elaboration procedure or a spec or
-- a body, referred to as elaboration root.
type Elaboration_Root_Iterator is private;
function Has_Next (Iter : Elaboration_Root_Iterator) return Boolean;
pragma Inline (Has_Next);
-- Determine whether iterator Iter has more elaboration roots to examine
function Iterate_Elaboration_Roots
(G : Invocation_Graph) return Elaboration_Root_Iterator;
pragma Inline (Iterate_Elaboration_Roots);
-- Obtain an iterator over all elaboration roots of invocation graph G
procedure Next
(Iter : in out Elaboration_Root_Iterator;
Root : out Invocation_Graph_Vertex_Id);
pragma Inline (Next);
-- Return the current elaboration root referenced by iterator Iter and
-- advance to the next available elaboration root.
private
--------------
-- Vertices --
--------------
procedure Destroy_Invocation_Graph_Vertex
(Vertex : in out Invocation_Graph_Vertex_Id);
pragma Inline (Destroy_Invocation_Graph_Vertex);
-- Destroy invocation graph vertex Vertex
-- The following type represents the attributes of an invocation graph
-- vertex.
type Invocation_Graph_Vertex_Attributes is record
Body_Vertex : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
-- Reference to the library graph vertex where the body of this
-- vertex resides.
Construct : Invocation_Construct_Id := No_Invocation_Construct;
-- Reference to the invocation construct this vertex represents
Spec_Vertex : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
-- Reference to the library graph vertex where the spec of this
-- vertex resides.
end record;
No_Invocation_Graph_Vertex_Attributes :
constant Invocation_Graph_Vertex_Attributes :=
(Body_Vertex => No_Library_Graph_Vertex,
Construct => No_Invocation_Construct,
Spec_Vertex => No_Library_Graph_Vertex);
procedure Destroy_Invocation_Graph_Vertex_Attributes
(Attrs : in out Invocation_Graph_Vertex_Attributes);
pragma Inline (Destroy_Invocation_Graph_Vertex_Attributes);
-- Destroy the contents of attributes Attrs
package IGV_Tables is new Dynamic_Hash_Tables
(Key_Type => Invocation_Graph_Vertex_Id,
Value_Type => Invocation_Graph_Vertex_Attributes,
No_Value => No_Invocation_Graph_Vertex_Attributes,
Expansion_Threshold => 1.5,
Expansion_Factor => 2,
Compression_Threshold => 0.3,
Compression_Factor => 2,
"=" => "=",
Destroy_Value => Destroy_Invocation_Graph_Vertex_Attributes,
Hash => Hash_Invocation_Graph_Vertex);
-----------
-- Edges --
-----------
procedure Destroy_Invocation_Graph_Edge
(Edge : in out Invocation_Graph_Edge_Id);
pragma Inline (Destroy_Invocation_Graph_Edge);
-- Destroy invocation graph edge Edge
-- The following type represents the attributes of an invocation graph
-- edge.
type Invocation_Graph_Edge_Attributes is record
Relation : Invocation_Relation_Id := No_Invocation_Relation;
-- Reference to the invocation relation this edge represents
end record;
No_Invocation_Graph_Edge_Attributes :
constant Invocation_Graph_Edge_Attributes :=
(Relation => No_Invocation_Relation);
procedure Destroy_Invocation_Graph_Edge_Attributes
(Attrs : in out Invocation_Graph_Edge_Attributes);
pragma Inline (Destroy_Invocation_Graph_Edge_Attributes);
-- Destroy the contents of attributes Attrs
package IGE_Tables is new Dynamic_Hash_Tables
(Key_Type => Invocation_Graph_Edge_Id,
Value_Type => Invocation_Graph_Edge_Attributes,
No_Value => No_Invocation_Graph_Edge_Attributes,
Expansion_Threshold => 1.5,
Expansion_Factor => 2,
Compression_Threshold => 0.3,
Compression_Factor => 2,
"=" => "=",
Destroy_Value => Destroy_Invocation_Graph_Edge_Attributes,
Hash => Hash_Invocation_Graph_Edge);
---------------
-- Relations --
---------------
-- The following type represents a relation between a source and target
-- vertices.
type Source_Target_Relation is record
Source : Invocation_Graph_Vertex_Id := No_Invocation_Graph_Vertex;
-- The source vertex
Target : Invocation_Graph_Vertex_Id := No_Invocation_Graph_Vertex;
-- The destination vertex
end record;
No_Source_Target_Relation :
constant Source_Target_Relation :=
(Source => No_Invocation_Graph_Vertex,
Target => No_Invocation_Graph_Vertex);
function Hash_Source_Target_Relation
(Rel : Source_Target_Relation) return Bucket_Range_Type;
pragma Inline (Hash_Source_Target_Relation);
-- Obtain the hash value of key Rel
package Relation_Sets is new Membership_Sets
(Element_Type => Source_Target_Relation,
"=" => "=",
Hash => Hash_Source_Target_Relation);
----------------
-- Statistics --
----------------
type Invocation_Graph_Edge_Counts is array (Invocation_Kind) of Natural;
----------------
-- Signatures --
----------------
function Hash_Invocation_Signature
(IS_Id : Invocation_Signature_Id) return Bucket_Range_Type;
pragma Inline (Hash_Invocation_Signature);
-- Obtain the hash value of key IS_Id
package Signature_Tables is new Dynamic_Hash_Tables
(Key_Type => Invocation_Signature_Id,
Value_Type => Invocation_Graph_Vertex_Id,
No_Value => No_Invocation_Graph_Vertex,
Expansion_Threshold => 1.5,
Expansion_Factor => 2,
Compression_Threshold => 0.3,
Compression_Factor => 2,
"=" => "=",
Destroy_Value => Destroy_Invocation_Graph_Vertex,
Hash => Hash_Invocation_Signature);
-----------------------
-- Elaboration roots --
-----------------------
package IGV_Sets is new Membership_Sets
(Element_Type => Invocation_Graph_Vertex_Id,
"=" => "=",
Hash => Hash_Invocation_Graph_Vertex);
-----------
-- Graph --
-----------
package DG is new Directed_Graphs
(Vertex_Id => Invocation_Graph_Vertex_Id,
No_Vertex => No_Invocation_Graph_Vertex,
Hash_Vertex => Hash_Invocation_Graph_Vertex,
Same_Vertex => "=",
Edge_id => Invocation_Graph_Edge_Id,
No_Edge => No_Invocation_Graph_Edge,
Hash_Edge => Hash_Invocation_Graph_Edge,
Same_Edge => "=");
-- The following type represents the attributes of an invocation graph
type Invocation_Graph_Attributes is record
Counts : Invocation_Graph_Edge_Counts := (others => 0);
-- Edge statistics
Edge_Attributes : IGE_Tables.Dynamic_Hash_Table := IGE_Tables.Nil;
-- The map of edge -> edge attributes for all edges in the graph
Graph : DG.Directed_Graph := DG.Nil;
-- The underlying graph describing the relations between edges and
-- vertices.
Relations : Relation_Sets.Membership_Set := Relation_Sets.Nil;
-- The set of relations between source and targets, used to prevent
-- duplicate edges in the graph.
Roots : IGV_Sets.Membership_Set := IGV_Sets.Nil;
-- The set of elaboration root vertices
Signature_To_Vertex : Signature_Tables.Dynamic_Hash_Table :=
Signature_Tables.Nil;
-- The map of signature -> vertex
Vertex_Attributes : IGV_Tables.Dynamic_Hash_Table := IGV_Tables.Nil;
-- The map of vertex -> vertex attributes for all vertices in the
-- graph.
Lib_Graph : Library_Graphs.Library_Graph;
end record;
type Invocation_Graph is access Invocation_Graph_Attributes;
Nil : constant Invocation_Graph := null;
---------------
-- Iterators --
---------------
type All_Edge_Iterator is new DG.All_Edge_Iterator;
type All_Vertex_Iterator is new DG.All_Vertex_Iterator;
type Edges_To_Targets_Iterator is new DG.Outgoing_Edge_Iterator;
type Elaboration_Root_Iterator is new IGV_Sets.Iterator;
end Invocation_Graphs;
end Bindo.Graphs;