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