------------------------------------------------------------------------------ | |

-- -- | |

-- 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; |