------------------------------------------------------------------------------ -- -- -- GNAT COMPILER COMPONENTS -- -- -- -- B I N D O . G R A P H S -- -- -- -- S p e c -- -- -- -- Copyright (C) 2019-2022, 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;