gcc/ada/bindo-graphs.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT COMPILER COMPONENTS                         --
   4 --                                                                          --
   5 --                         B I N D O . G R A P H S                          --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --             Copyright (C) 2019-2023, Free Software Foundation, Inc.      --
  10 --                                                                          --
  11 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  12 -- terms of the  GNU General Public License as published  by the Free Soft- --
  13 -- ware  Foundation;  either version 3,  or (at your option) any later ver- --
  14 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  15 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  16 -- or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License --
  17 -- for  more details.  You should have  received  a copy of the GNU General --
  18 -- Public License  distributed with GNAT; see file COPYING3.  If not, go to --
  19 -- http://www.gnu.org/licenses for a complete copy of the license.          --
  20 --                                                                          --
  21 -- GNAT was originally developed  by the GNAT team at  New York University. --
  22 -- Extensive contributions were provided by Ada Core Technologies Inc.      --
  23 --                                                                          --
  24 ------------------------------------------------------------------------------
  25
  26 --  For full architecture, see unit Bindo.
  27
  28 --  The following unit defines the various graphs used in determining the
  29 --  elaboration order of units.
  30
  31 with Types; use Types;
  32
  33 with Bindo.Units; use Bindo.Units;
  34
  35 with GNAT;                 use GNAT;
  36 with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables;
  37 with GNAT.Graphs;          use GNAT.Graphs;
  38 with GNAT.Lists;           use GNAT.Lists;
  39 with GNAT.Sets;            use GNAT.Sets;
  40
  41 package Bindo.Graphs is
  42
  43    ---------------------------
  44    -- Invocation graph edge --
  45    ---------------------------
  46
  47    --  The following type denotes an invocation graph edge handle
  48
  49    type Invocation_Graph_Edge_Id is new Natural;
  50    No_Invocation_Graph_Edge    : constant Invocation_Graph_Edge_Id :=
  51                                    Invocation_Graph_Edge_Id'First;
  52    First_Invocation_Graph_Edge : constant Invocation_Graph_Edge_Id :=
  53                                    No_Invocation_Graph_Edge + 1;
  54
  55    procedure Destroy_Invocation_Graph_Edge
  56      (Edge : in out Invocation_Graph_Edge_Id);
  57    pragma Inline (Destroy_Invocation_Graph_Edge);
  58    --  Destroy invocation graph edge Edge
  59
  60    function Hash_Invocation_Graph_Edge
  61      (Edge : Invocation_Graph_Edge_Id) return Bucket_Range_Type;
  62    pragma Inline (Hash_Invocation_Graph_Edge);
  63    --  Obtain the hash value of key Edge
  64
  65    function Present (Edge : Invocation_Graph_Edge_Id) return Boolean;
  66    pragma Inline (Present);
  67    --  Determine whether invocation graph edge Edge exists
  68
  69    package IGE_Lists is new Doubly_Linked_Lists
  70      (Element_Type    => Invocation_Graph_Edge_Id,
  71       "="             => "=",
  72       Destroy_Element => Destroy_Invocation_Graph_Edge);
  73
  74    ------------------------------
  75    --  Invocation graph vertex --
  76    ------------------------------
  77
  78    --  The following type denotes an invocation graph vertex handle
  79
  80    type Invocation_Graph_Vertex_Id is new Natural;
  81    No_Invocation_Graph_Vertex    : constant Invocation_Graph_Vertex_Id :=
  82                                      Invocation_Graph_Vertex_Id'First;
  83    First_Invocation_Graph_Vertex : constant Invocation_Graph_Vertex_Id :=
  84                                      No_Invocation_Graph_Vertex + 1;
  85
  86    function Hash_Invocation_Graph_Vertex
  87      (Vertex : Invocation_Graph_Vertex_Id) return Bucket_Range_Type;
  88    pragma Inline (Hash_Invocation_Graph_Vertex);
  89    --  Obtain the hash value of key Vertex
  90
  91    function Present (Vertex : Invocation_Graph_Vertex_Id) return Boolean;
  92    pragma Inline (Present);
  93    --  Determine whether invocation graph vertex Vertex exists
  94
  95    package IGV_Sets is new Membership_Sets
  96      (Element_Type => Invocation_Graph_Vertex_Id,
  97       "="          => "=",
  98       Hash         => Hash_Invocation_Graph_Vertex);
  99
 100    -------------------------
 101    -- Library graph cycle --
 102    -------------------------
 103
 104    type Library_Graph_Cycle_Id is new Natural;
 105    No_Library_Graph_Cycle    : constant Library_Graph_Cycle_Id :=
 106                                  Library_Graph_Cycle_Id'First;
 107    First_Library_Graph_Cycle : constant Library_Graph_Cycle_Id :=
 108                                  No_Library_Graph_Cycle + 1;
 109
 110    procedure Destroy_Library_Graph_Cycle
 111      (Cycle : in out Library_Graph_Cycle_Id);
 112    pragma Inline (Destroy_Library_Graph_Cycle);
 113    --  Destroy library graph cycle Cycle
 114
 115    function Hash_Library_Graph_Cycle
 116      (Cycle : Library_Graph_Cycle_Id) return Bucket_Range_Type;
 117    pragma Inline (Hash_Library_Graph_Cycle);
 118    --  Obtain the hash value of key Cycle
 119
 120    function Present (Cycle : Library_Graph_Cycle_Id) return Boolean;
 121    pragma Inline (Present);
 122    --  Determine whether library graph cycle Cycle exists
 123
 124    package LGC_Lists is new Doubly_Linked_Lists
 125      (Element_Type    => Library_Graph_Cycle_Id,
 126       "="             => "=",
 127       Destroy_Element => Destroy_Library_Graph_Cycle);
 128
 129    ------------------------
 130    -- Library graph edge --
 131    ------------------------
 132
 133    --  The following type denotes a library graph edge handle
 134
 135    type Library_Graph_Edge_Id is new Natural;
 136    No_Library_Graph_Edge    : constant Library_Graph_Edge_Id :=
 137                                 Library_Graph_Edge_Id'First;
 138    First_Library_Graph_Edge : constant Library_Graph_Edge_Id :=
 139                                 No_Library_Graph_Edge + 1;
 140
 141    procedure Destroy_Library_Graph_Edge
 142      (Edge : in out Library_Graph_Edge_Id);
 143    pragma Inline (Destroy_Library_Graph_Edge);
 144    --  Destroy library graph edge Edge
 145
 146    function Hash_Library_Graph_Edge
 147      (Edge : Library_Graph_Edge_Id) return Bucket_Range_Type;
 148    pragma Inline (Hash_Library_Graph_Edge);
 149    --  Obtain the hash value of key Edge
 150
 151    function Present (Edge : Library_Graph_Edge_Id) return Boolean;
 152    pragma Inline (Present);
 153    --  Determine whether library graph edge Edge exists
 154
 155    package LGE_Lists is new Doubly_Linked_Lists
 156      (Element_Type    => Library_Graph_Edge_Id,
 157       "="             => "=",
 158       Destroy_Element => Destroy_Library_Graph_Edge);
 159
 160    package LGE_Sets is new Membership_Sets
 161      (Element_Type => Library_Graph_Edge_Id,
 162       "="          => "=",
 163       Hash         => Hash_Library_Graph_Edge);
 164
 165    --------------------------
 166    -- Library graph vertex --
 167    --------------------------
 168
 169    --  The following type denotes a library graph vertex handle
 170
 171    type Library_Graph_Vertex_Id is new Natural;
 172    No_Library_Graph_Vertex    : constant Library_Graph_Vertex_Id :=
 173                                   Library_Graph_Vertex_Id'First;
 174    First_Library_Graph_Vertex : constant Library_Graph_Vertex_Id :=
 175                                   No_Library_Graph_Vertex + 1;
 176
 177    procedure Destroy_Library_Graph_Vertex
 178      (Vertex : in out Library_Graph_Vertex_Id);
 179    pragma Inline (Destroy_Library_Graph_Vertex);
 180    --  Destroy library graph vertex Vertex
 181
 182    function Hash_Library_Graph_Vertex
 183      (Vertex : Library_Graph_Vertex_Id) return Bucket_Range_Type;
 184    pragma Inline (Hash_Library_Graph_Vertex);
 185    --  Obtain the hash value of key Vertex
 186
 187    function Present (Vertex : Library_Graph_Vertex_Id) return Boolean;
 188    pragma Inline (Present);
 189    --  Determine whether library graph vertex Vertex exists
 190
 191    package LGV_Lists is new Doubly_Linked_Lists
 192      (Element_Type    => Library_Graph_Vertex_Id,
 193       "="             => "=",
 194       Destroy_Element => Destroy_Library_Graph_Vertex);
 195
 196    package LGV_Sets is new Membership_Sets
 197      (Element_Type => Library_Graph_Vertex_Id,
 198       "="          => "=",
 199       Hash         => Hash_Library_Graph_Vertex);
 200
 201    --------------------
 202    -- Library_Graphs --
 203    --------------------
 204
 205    package Library_Graphs is
 206
 207       --  The following type represents the various kinds of library graph
 208       --  cycles. The ordering of kinds is significant, where a literal with
 209       --  lower ordinal has a higher precedence than one with higher ordinal.
 210
 211       type Library_Graph_Cycle_Kind is
 212         (Elaborate_Body_Cycle,
 213          --  A cycle that involves at least one spec-body pair, where the
 214          --  spec is subject to pragma Elaborate_Body. This is the highest
 215          --  precedence cycle.
 216
 217          Elaborate_Cycle,
 218          --  A cycle that involves at least one Elaborate edge
 219
 220          Elaborate_All_Cycle,
 221          --  A cycle that involves at least one Elaborate_All edge
 222
 223          Forced_Cycle,
 224          --  A cycle that involves at least one edge which is a byproduct of
 225          --  the forced-elaboration-order file.
 226
 227          Invocation_Cycle,
 228          --  A cycle that involves at least one invocation edge. This is the
 229          --  lowest precedence cycle.
 230
 231          No_Cycle_Kind);
 232
 233       --  The following type represents the various kinds of library edges. The
 234       --  order is important here, and corresponds to the order in which edges
 235       --  are added to the graph. See Add_Edge_Kind_Check for details. If
 236       --  changes are made such that new edge kinds are added or similar, we
 237       --  need to make sure this type matches the code in Add_Edge_Kind_Check,
 238       --  and Add_Edge_Kind_Check matches the order of edge adding. Likewise,
 239       --  if the edge-adding order changes, we need consistency between this
 240       --  enumeration type, the edge-adding order, and Add_Edge_Kind_Check.
 241
 242       type Library_Graph_Edge_Kind is
 243         (Spec_Before_Body_Edge,
 244          --  Successor denotes a body, Predecessor denotes a spec
 245
 246          Elaborate_Edge,
 247          --  Successor withs Predecessor, and has pragma Elaborate for it
 248
 249          Elaborate_All_Edge,
 250          --  Successor withs Predecessor, and has pragma Elaborate_All for it
 251
 252          With_Edge,
 253          --  Successor withs Predecessor
 254
 255          Forced_Edge,
 256          --  Successor is forced to with Predecessor by virtue of an existing
 257          --  elaboration order provided in a file.
 258
 259          Invocation_Edge,
 260          --  An invocation construct in unit Successor invokes a target in unit
 261          --  Predecessor.
 262
 263          Body_Before_Spec_Edge,
 264          --  Successor denotes spec, Predecessor denotes a body. This is a
 265          --  special edge kind used only during the discovery of components.
 266          --  Note that a body can never be elaborated before its spec.
 267
 268          No_Edge);
 269
 270       -----------
 271       -- Graph --
 272       -----------
 273
 274       --  The following type denotes a library graph handle. Each instance must
 275       --  be created using routine Create.
 276
 277       type Library_Graph is private;
 278       Nil : constant Library_Graph;
 279
 280       type LGE_Predicate_Ptr is access function
 281         (G    : Library_Graph;
 282          Edge : Library_Graph_Edge_Id) return Boolean;
 283
 284       type LGV_Comparator_Ptr is access function
 285         (G           : Library_Graph;
 286          Vertex      : Library_Graph_Vertex_Id;
 287          Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind;
 288
 289       type LGV_Predicate_Ptr is access function
 290         (G      : Library_Graph;
 291          Vertex : Library_Graph_Vertex_Id) return Boolean;
 292
 293       ----------------------
 294       -- Graph operations --
 295       ----------------------
 296
 297       procedure Add_Edge
 298         (G              : Library_Graph;
 299          Pred           : Library_Graph_Vertex_Id;
 300          Succ           : Library_Graph_Vertex_Id;
 301          Kind           : Library_Graph_Edge_Kind;
 302          Activates_Task : Boolean);
 303       pragma Inline (Add_Edge);
 304       --  Create a new edge in library graph G with source vertex Pred and
 305       --  destination vertex Succ. Kind denotes the nature of the edge. Flag
 306       --  Activates_Task should be set when the edge involves task activation.
 307
 308       procedure Add_Vertex
 309         (G    : Library_Graph;
 310          U_Id : Unit_Id);
 311       pragma Inline (Add_Vertex);
 312       --  Create a new vertex in library graph G. U_Id is the unit the vertex
 313       --  describes.
 314
 315       function Create
 316         (Initial_Vertices : Positive;
 317          Initial_Edges    : Positive) return Library_Graph;
 318       pragma Inline (Create);
 319       --  Create a new empty graph with vertex capacity Initial_Vertices and
 320       --  edge capacity Initial_Edges.
 321
 322       procedure Destroy (G : in out Library_Graph);
 323       pragma Inline (Destroy);
 324       --  Destroy the contents of library graph G, rendering it unusable
 325
 326       procedure Find_Components (G : Library_Graph);
 327       pragma Inline (Find_Components);
 328       --  Find all components in library graph G
 329
 330       procedure Find_Cycles (G : Library_Graph);
 331       pragma Inline (Find_Cycles);
 332       --  Find all cycles in library graph G
 333
 334       function Highest_Precedence_Cycle
 335         (G : Library_Graph) return Library_Graph_Cycle_Id;
 336       pragma Inline (Highest_Precedence_Cycle);
 337       --  Obtain the cycle with highest precedence among all other cycles of
 338       --  library graph G.
 339
 340       function Present (G : Library_Graph) return Boolean;
 341       pragma Inline (Present);
 342       --  Determine whether library graph G exists
 343
 344       -----------------------
 345       -- Vertex attributes --
 346       -----------------------
 347
 348       function Component
 349         (G      : Library_Graph;
 350          Vertex : Library_Graph_Vertex_Id) return Component_Id;
 351       pragma Inline (Component);
 352       --  Obtain the component where vertex Vertex of library graph G resides
 353
 354       function Corresponding_Item
 355         (G      : Library_Graph;
 356          Vertex : Library_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
 357       pragma Inline (Corresponding_Item);
 358       --  Obtain the complementary vertex which represents the corresponding
 359       --  spec or body of vertex Vertex of library graph G.
 360
 361       function Corresponding_Vertex
 362         (G    : Library_Graph;
 363          U_Id : Unit_Id) return Library_Graph_Vertex_Id;
 364       pragma Inline (Corresponding_Vertex);
 365       --  Obtain the corresponding vertex of library graph G which represents
 366       --  unit U_Id.
 367
 368       procedure Decrement_Pending_Predecessors
 369         (G      : Library_Graph;
 370          Vertex : Library_Graph_Vertex_Id;
 371          Edge   : Library_Graph_Edge_Id);
 372       pragma Inline (Decrement_Pending_Predecessors);
 373       --  Decrease the number of pending predecessors vertex Vertex which was
 374       --  reached via edge Edge of library graph G must wait until it can be
 375       --  elaborated.
 376
 377       function File_Name
 378         (G      : Library_Graph;
 379          Vertex : Library_Graph_Vertex_Id) return File_Name_Type;
 380       pragma Inline (File_Name);
 381       --  Obtain the name of the file where vertex Vertex of library graph G
 382       --  resides.
 383
 384       function In_Elaboration_Order
 385         (G      : Library_Graph;
 386          Vertex : Library_Graph_Vertex_Id) return Boolean;
 387       pragma Inline (In_Elaboration_Order);
 388       --  Determine whether vertex Vertex of library graph G is already in some
 389       --  elaboration order.
 390
 391       function Invocation_Graph_Encoding
 392         (G      : Library_Graph;
 393          Vertex : Library_Graph_Vertex_Id)
 394          return Invocation_Graph_Encoding_Kind;
 395       pragma Inline (Invocation_Graph_Encoding);
 396       --  Obtain the encoding format used to capture information related to
 397       --  invocation vertices and edges that reside within vertex Vertex of
 398       --  library graph G.
 399
 400       function Name
 401         (G      : Library_Graph;
 402          Vertex : Library_Graph_Vertex_Id) return Unit_Name_Type;
 403       pragma Inline (Name);
 404       --  Obtain the name of the unit which vertex Vertex of library graph G
 405       --  represents.
 406
 407       procedure Pending_Predecessors_For_Elaboration
 408         (G            : Library_Graph;
 409          Vertex       : Library_Graph_Vertex_Id;
 410          Strong_Preds : out Natural;
 411          Weak_Preds   : out Natural);
 412       pragma Inline (Pending_Predecessors_For_Elaboration);
 413       --  Obtain the number of pending strong and weak predecessors of vertex
 414       --  Vertex of library graph G, taking into account Elaborate_Body pairs.
 415       --  Strong predecessors are returned in Strong_Preds. Weak predecessors
 416       --  are returned in Weak_Preds.
 417
 418       function Pending_Strong_Predecessors
 419         (G      : Library_Graph;
 420          Vertex : Library_Graph_Vertex_Id) return Natural;
 421       pragma Inline (Pending_Strong_Predecessors);
 422       --  Obtain the number of pending strong predecessors vertex Vertex of
 423       --  library graph G must wait on until it can be elaborated.
 424
 425       function Pending_Weak_Predecessors
 426         (G      : Library_Graph;
 427          Vertex : Library_Graph_Vertex_Id) return Natural;
 428       pragma Inline (Pending_Weak_Predecessors);
 429       --  Obtain the number of pending weak predecessors vertex Vertex of
 430       --  library graph G must wait on until it can be elaborated.
 431
 432       procedure Set_Corresponding_Item
 433         (G      : Library_Graph;
 434          Vertex : Library_Graph_Vertex_Id;
 435          Val    : Library_Graph_Vertex_Id);
 436       pragma Inline (Set_Corresponding_Item);
 437       --  Set the complementary vertex which represents the corresponding
 438       --  spec or body of vertex Vertex of library graph G to value Val.
 439
 440       procedure Set_In_Elaboration_Order
 441         (G      : Library_Graph;
 442          Vertex : Library_Graph_Vertex_Id;
 443          Val    : Boolean := True);
 444       pragma Inline (Set_In_Elaboration_Order);
 445       --  Mark vertex Vertex of library graph G as included in some elaboration
 446       --  order depending on value Val.
 447
 448       function Unit
 449         (G      : Library_Graph;
 450          Vertex : Library_Graph_Vertex_Id) return Unit_Id;
 451       pragma Inline (Unit);
 452       --  Obtain the unit vertex Vertex of library graph G represents
 453
 454       ---------------------
 455       -- Edge attributes --
 456       ---------------------
 457
 458       function Activates_Task
 459         (G    : Library_Graph;
 460          Edge : Library_Graph_Edge_Id) return Boolean;
 461       pragma Inline (Activates_Task);
 462       --  Determine whether edge Edge of library graph G activates a task
 463
 464       function Kind
 465         (G    : Library_Graph;
 466          Edge : Library_Graph_Edge_Id) return Library_Graph_Edge_Kind;
 467       pragma Inline (Kind);
 468       --  Obtain the nature of edge Edge of library graph G
 469
 470       function Predecessor
 471         (G    : Library_Graph;
 472          Edge : Library_Graph_Edge_Id) return Library_Graph_Vertex_Id;
 473       pragma Inline (Predecessor);
 474       --  Obtain the predecessor vertex of edge Edge of library graph G
 475
 476       function Successor
 477         (G    : Library_Graph;
 478          Edge : Library_Graph_Edge_Id) return Library_Graph_Vertex_Id;
 479       pragma Inline (Successor);
 480       --  Obtain the successor vertex of edge Edge of library graph G
 481
 482       --------------------------
 483       -- Component attributes --
 484       --------------------------
 485
 486       procedure Decrement_Pending_Predecessors
 487         (G    : Library_Graph;
 488          Comp : Component_Id;
 489          Edge : Library_Graph_Edge_Id);
 490       pragma Inline (Decrement_Pending_Predecessors);
 491       --  Decrease the number of pending predecessors component Comp which was
 492       --  reached via edge Edge of library graph G must wait on until it can be
 493       --  elaborated.
 494
 495       function Pending_Strong_Predecessors
 496         (G    : Library_Graph;
 497          Comp : Component_Id) return Natural;
 498       pragma Inline (Pending_Strong_Predecessors);
 499       --  Obtain the number of pending strong predecessors component Comp of
 500       --  library graph G must wait on until it can be elaborated.
 501
 502       function Pending_Weak_Predecessors
 503         (G    : Library_Graph;
 504          Comp : Component_Id) return Natural;
 505       pragma Inline (Pending_Weak_Predecessors);
 506       --  Obtain the number of pending weak predecessors component Comp of
 507       --  library graph G must wait on until it can be elaborated.
 508
 509       ----------------------
 510       -- Cycle attributes --
 511       ----------------------
 512
 513       function Invocation_Edge_Count
 514         (G      : Library_Graph;
 515          Cycle : Library_Graph_Cycle_Id) return Natural;
 516       pragma Inline (Invocation_Edge_Count);
 517       --  Obtain the number of invocation edges in cycle Cycle of library
 518       --  graph G.
 519
 520       function Kind
 521         (G     : Library_Graph;
 522          Cycle : Library_Graph_Cycle_Id) return Library_Graph_Cycle_Kind;
 523       pragma Inline (Kind);
 524       --  Obtain the nature of cycle Cycle of library graph G
 525
 526       function Length
 527         (G     : Library_Graph;
 528          Cycle : Library_Graph_Cycle_Id) return Natural;
 529       pragma Inline (Length);
 530       --  Obtain the length of cycle Cycle of library graph G
 531
 532       ---------------
 533       -- Semantics --
 534       ---------------
 535
 536       function Complementary_Vertex
 537         (G                : Library_Graph;
 538          Vertex           : Library_Graph_Vertex_Id;
 539          Force_Complement : Boolean) return Library_Graph_Vertex_Id;
 540       pragma Inline (Complementary_Vertex);
 541       --  Obtain the complementary vertex of vertex Vertex of library graph G
 542       --  as follows:
 543       --
 544       --    * If Vertex is the spec of an Elaborate_Body pair, return the body
 545       --    * If Vertex is the body of an Elaborate_Body pair, return the spec
 546       --
 547       --  This behavior can be forced by setting flag Force_Complement to True.
 548
 549       function Contains_Elaborate_All_Edge
 550         (G     : Library_Graph;
 551          Cycle : Library_Graph_Cycle_Id) return Boolean;
 552       pragma Inline (Contains_Elaborate_All_Edge);
 553       --  Determine whether cycle Cycle of library graph G contains an
 554       --  Elaborate_All edge.
 555
 556       function Contains_Static_Successor_Edge
 557         (G     : Library_Graph;
 558          Cycle : Library_Graph_Cycle_Id) return Boolean;
 559       pragma Inline (Contains_Static_Successor_Edge);
 560       --  Determine whether cycle Cycle of library graph G contains an edge
 561       --  where the successor was compiled using the static model.
 562
 563       function Contains_Task_Activation
 564         (G     : Library_Graph;
 565          Cycle : Library_Graph_Cycle_Id) return Boolean;
 566       pragma Inline (Contains_Task_Activation);
 567       --  Determine whether cycle Cycle of library graph G contains an
 568       --  invocation edge where the path it represents involves a task
 569       --  activation.
 570
 571       function Has_Elaborate_All_Cycle (G : Library_Graph) return Boolean;
 572       pragma Inline (Has_Elaborate_All_Cycle);
 573       --  Determine whether library graph G contains a cycle involving pragma
 574       --  Elaborate_All.
 575
 576       function Has_No_Elaboration_Code
 577         (G      : Library_Graph;
 578          Vertex : Library_Graph_Vertex_Id) return Boolean;
 579       pragma Inline (Has_No_Elaboration_Code);
 580       --  Determine whether vertex Vertex of library graph G represents a unit
 581       --  that lacks elaboration code.
 582
 583       function In_Same_Component
 584         (G     : Library_Graph;
 585          Left  : Library_Graph_Vertex_Id;
 586          Right : Library_Graph_Vertex_Id) return Boolean;
 587       pragma Inline (In_Same_Component);
 588       --  Determine whether vertices Left and Right of library graph G reside
 589       --  in the same component.
 590
 591       function Is_Body
 592         (G      : Library_Graph;
 593          Vertex : Library_Graph_Vertex_Id) return Boolean;
 594       pragma Inline (Is_Body);
 595       --  Determine whether vertex Vertex of library graph G denotes a body
 596
 597       function Is_Body_Of_Spec_With_Elaborate_Body
 598         (G      : Library_Graph;
 599          Vertex : Library_Graph_Vertex_Id) return Boolean;
 600       pragma Inline (Is_Body_Of_Spec_With_Elaborate_Body);
 601       --  Determine whether vertex Vertex of library graph G denotes a body
 602       --  with a corresponding spec, and the spec has pragma Elaborate_Body.
 603
 604       function Is_Body_With_Spec
 605         (G      : Library_Graph;
 606          Vertex : Library_Graph_Vertex_Id) return Boolean;
 607       pragma Inline (Is_Body_With_Spec);
 608       --  Determine whether vertex Vertex of library graph G denotes a body
 609       --  with a corresponding spec.
 610
 611       function Is_Dynamically_Elaborated
 612         (G      : Library_Graph;
 613          Vertex : Library_Graph_Vertex_Id) return Boolean;
 614       pragma Inline (Is_Dynamically_Elaborated);
 615       --  Determine whether vertex Vertex of library graph G was compiled
 616       --  using the dynamic model.
 617
 618       function Is_Elaborable_Component
 619         (G    : Library_Graph;
 620          Comp : Component_Id) return Boolean;
 621       pragma Inline (Is_Elaborable_Component);
 622       --  Determine whether component Comp of library graph G is not waiting on
 623       --  any predecessors, and can thus be elaborated.
 624
 625       function Is_Elaborable_Vertex
 626         (G      : Library_Graph;
 627          Vertex : Library_Graph_Vertex_Id) return Boolean;
 628       pragma Inline (Is_Elaborable_Vertex);
 629       --  Determine whether vertex Vertex of library graph G is not waiting on
 630       --  any predecessors, and can thus be elaborated.
 631
 632       function Is_Elaborate_All_Edge
 633         (G    : Library_Graph;
 634          Edge : Library_Graph_Edge_Id) return Boolean;
 635       pragma Inline (Is_Elaborate_All_Edge);
 636       --  Determine whether edge Edge of library graph G is an edge whose
 637       --  predecessor is subject to pragma Elaborate_All.
 638
 639       function Is_Elaborate_Body_Edge
 640         (G    : Library_Graph;
 641          Edge : Library_Graph_Edge_Id) return Boolean;
 642       pragma Inline (Is_Elaborate_Body_Edge);
 643       --  Determine whether edge Edge of library graph G has a successor
 644       --  that is either a spec subject to pragma Elaborate_Body, or a body
 645       --  that completes such a spec.
 646
 647       function Is_Elaborate_Edge
 648         (G    : Library_Graph;
 649          Edge : Library_Graph_Edge_Id) return Boolean;
 650       pragma Inline (Is_Elaborate_Edge);
 651       --  Determine whether edge Edge of library graph G is an edge whose
 652       --  predecessor is subject to pragma Elaborate.
 653
 654       function Is_Elaborate_Body_Pair
 655         (G           : Library_Graph;
 656          Spec_Vertex : Library_Graph_Vertex_Id;
 657          Body_Vertex : Library_Graph_Vertex_Id) return Boolean;
 658       pragma Inline (Is_Elaborate_Body_Pair);
 659       --  Determine whether vertices Spec_Vertex and Body_Vertex of library
 660       --  graph G denote a spec subject to Elaborate_Body and its completing
 661       --  body.
 662
 663       function Is_Forced_Edge
 664         (G    : Library_Graph;
 665          Edge : Library_Graph_Edge_Id) return Boolean;
 666       pragma Inline (Is_Forced_Edge);
 667       --  Determine whether edge Edge of library graph G is a byproduct of the
 668       --  forced-elaboration-order file.
 669
 670       function Is_Internal_Unit
 671         (G      : Library_Graph;
 672          Vertex : Library_Graph_Vertex_Id) return Boolean;
 673       pragma Inline (Is_Internal_Unit);
 674       --  Determine whether vertex Vertex of library graph G denotes an
 675       --  internal unit.
 676
 677       function Is_Invocation_Edge
 678         (G    : Library_Graph;
 679          Edge : Library_Graph_Edge_Id) return Boolean;
 680       pragma Inline (Is_Invocation_Edge);
 681       --  Determine whether edge Edge of library graph G came from the
 682       --  traversal of the invocation graph.
 683
 684       function Is_Predefined_Unit
 685         (G      : Library_Graph;
 686          Vertex : Library_Graph_Vertex_Id) return Boolean;
 687       pragma Inline (Is_Predefined_Unit);
 688       --  Determine whether vertex Vertex of library graph G denotes a
 689       --  predefined unit.
 690
 691       function Is_Preelaborated_Unit
 692         (G      : Library_Graph;
 693          Vertex : Library_Graph_Vertex_Id) return Boolean;
 694       pragma Inline (Is_Preelaborated_Unit);
 695       --  Determine whether vertex Vertex of library graph G denotes a unit
 696       --  subject to pragma Pure or Preelaborable.
 697
 698       function Is_Spec
 699         (G      : Library_Graph;
 700          Vertex : Library_Graph_Vertex_Id) return Boolean;
 701       pragma Inline (Is_Spec);
 702       --  Determine whether vertex Vertex of library graph G denotes a spec
 703
 704       function Is_Spec_Before_Body_Edge
 705         (G    : Library_Graph;
 706          Edge : Library_Graph_Edge_Id) return Boolean;
 707       pragma Inline (Is_Spec_Before_Body_Edge);
 708       --  Determine whether edge Edge of library graph G links a predecessor
 709       --  spec and a successor body belonging to the same unit.
 710
 711       function Is_Spec_With_Body
 712         (G      : Library_Graph;
 713          Vertex : Library_Graph_Vertex_Id) return Boolean;
 714       pragma Inline (Is_Spec_With_Body);
 715       --  Determine whether vertex Vertex of library graph G denotes a spec
 716       --  with a corresponding body.
 717
 718       function Is_Spec_With_Elaborate_Body
 719         (G      : Library_Graph;
 720          Vertex : Library_Graph_Vertex_Id) return Boolean;
 721       pragma Inline (Is_Spec_With_Elaborate_Body);
 722       --  Determine whether vertex Vertex of library graph G denotes a spec
 723       --  with a corresponding body, and is subject to pragma Elaborate_Body.
 724
 725       function Is_Weakly_Elaborable_Vertex
 726         (G      : Library_Graph;
 727          Vertex : Library_Graph_Vertex_Id) return Boolean;
 728       pragma Inline (Is_Weakly_Elaborable_Vertex);
 729       --  Determine whether vertex Vertex of library graph G is waiting on
 730       --  weak predecessors only, in which case it can be elaborated assuming
 731       --  that the weak edges will not be exercised at elaboration time.
 732
 733       function Is_With_Edge
 734         (G    : Library_Graph;
 735          Edge : Library_Graph_Edge_Id) return Boolean;
 736       pragma Inline (Is_With_Edge);
 737       --  Determine whether edge Edge of library graph G is the result of a
 738       --  with dependency between its successor and predecessor.
 739
 740       function Needs_Elaboration
 741         (G      : Library_Graph;
 742          Vertex : Library_Graph_Vertex_Id) return Boolean;
 743       pragma Inline (Needs_Elaboration);
 744       --  Determine whether vertex Vertex of library graph G represents a unit
 745       --  that needs to be elaborated.
 746
 747       function Proper_Body
 748         (G      : Library_Graph;
 749          Vertex : Library_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
 750       pragma Inline (Proper_Body);
 751       --  Obtain the body of vertex Vertex of library graph G
 752
 753       function Proper_Spec
 754         (G      : Library_Graph;
 755          Vertex : Library_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
 756       pragma Inline (Proper_Spec);
 757       --  Obtain the spec of vertex Vertex of library graph G
 758
 759       ----------------
 760       -- Statistics --
 761       ----------------
 762
 763       function Library_Graph_Edge_Count
 764         (G    : Library_Graph;
 765          Kind : Library_Graph_Edge_Kind) return Natural;
 766       pragma Inline (Library_Graph_Edge_Count);
 767       --  Obtain the total number of edges of kind Kind in library graph G
 768
 769       function Number_Of_Component_Vertices
 770         (G    : Library_Graph;
 771          Comp : Component_Id) return Natural;
 772       pragma Inline (Number_Of_Component_Vertices);
 773       --  Obtain the total number of vertices component Comp of library graph
 774       --  contains.
 775
 776       function Number_Of_Components (G : Library_Graph) return Natural;
 777       pragma Inline (Number_Of_Components);
 778       --  Obtain the total number of components in library graph G
 779
 780       function Number_Of_Cycles (G : Library_Graph) return Natural;
 781       pragma Inline (Number_Of_Cycles);
 782       --  Obtain the total number of cycles in library graph G
 783
 784       function Number_Of_Edges (G : Library_Graph) return Natural;
 785       pragma Inline (Number_Of_Edges);
 786       --  Obtain the total number of edges in library graph G
 787
 788       function Number_Of_Edges_To_Successors
 789         (G      : Library_Graph;
 790          Vertex : Library_Graph_Vertex_Id) return Natural;
 791       pragma Inline (Number_Of_Edges_To_Successors);
 792       --  Obtain the total number of edges to successors vertex Vertex of
 793       --  library graph G has.
 794
 795       function Number_Of_Vertices (G : Library_Graph) return Natural;
 796       pragma Inline (Number_Of_Vertices);
 797       --  Obtain the total number of vertices in library graph G
 798
 799       ---------------
 800       -- Iterators --
 801       ---------------
 802
 803       --  The following type represents an iterator over all cycles of a
 804       --  library graph.
 805
 806       type All_Cycle_Iterator is private;
 807
 808       function Has_Next (Iter : All_Cycle_Iterator) return Boolean;
 809       pragma Inline (Has_Next);
 810       --  Determine whether iterator Iter has more cycles to examine
 811
 812       function Iterate_All_Cycles
 813         (G : Library_Graph) return All_Cycle_Iterator;
 814       pragma Inline (Iterate_All_Cycles);
 815       --  Obtain an iterator over all cycles of library graph G
 816
 817       procedure Next
 818         (Iter  : in out All_Cycle_Iterator;
 819          Cycle : out Library_Graph_Cycle_Id);
 820       pragma Inline (Next);
 821       --  Return the current cycle referenced by iterator Iter and advance to
 822       --  the next available cycle.
 823
 824       --  The following type represents an iterator over all edges of a library
 825       --  graph.
 826
 827       type All_Edge_Iterator is private;
 828
 829       function Has_Next (Iter : All_Edge_Iterator) return Boolean;
 830       pragma Inline (Has_Next);
 831       --  Determine whether iterator Iter has more edges to examine
 832
 833       function Iterate_All_Edges (G : Library_Graph) return All_Edge_Iterator;
 834       pragma Inline (Iterate_All_Edges);
 835       --  Obtain an iterator over all edges of library graph G
 836
 837       procedure Next
 838         (Iter : in out All_Edge_Iterator;
 839          Edge : out Library_Graph_Edge_Id);
 840       pragma Inline (Next);
 841       --  Return the current edge referenced by iterator Iter and advance to
 842       --  the next available edge.
 843
 844       --  The following type represents an iterator over all vertices of a
 845       --  library graph.
 846
 847       type All_Vertex_Iterator is private;
 848
 849       function Has_Next (Iter : All_Vertex_Iterator) return Boolean;
 850       pragma Inline (Has_Next);
 851       --  Determine whether iterator Iter has more vertices to examine
 852
 853       function Iterate_All_Vertices
 854         (G : Library_Graph) return All_Vertex_Iterator;
 855       pragma Inline (Iterate_All_Vertices);
 856       --  Obtain an iterator over all vertices of library graph G
 857
 858       procedure Next
 859         (Iter   : in out All_Vertex_Iterator;
 860          Vertex : out Library_Graph_Vertex_Id);
 861       pragma Inline (Next);
 862       --  Return the current vertex referenced by iterator Iter and advance
 863       --  to the next available vertex.
 864
 865       --  The following type represents an iterator over all components of a
 866       --  library graph.
 867
 868       type Component_Iterator is private;
 869
 870       function Has_Next (Iter : Component_Iterator) return Boolean;
 871       pragma Inline (Has_Next);
 872       --  Determine whether iterator Iter has more components to examine
 873
 874       function Iterate_Components
 875         (G : Library_Graph) return Component_Iterator;
 876       pragma Inline (Iterate_Components);
 877       --  Obtain an iterator over all components of library graph G
 878
 879       procedure Next
 880         (Iter : in out Component_Iterator;
 881          Comp : out Component_Id);
 882       pragma Inline (Next);
 883       --  Return the current component referenced by iterator Iter and advance
 884       --  to the next available component.
 885
 886       --  The following type represents an iterator over all vertices of a
 887       --  component.
 888
 889       type Component_Vertex_Iterator is private;
 890
 891       function Has_Next (Iter : Component_Vertex_Iterator) return Boolean;
 892       pragma Inline (Has_Next);
 893       --  Determine whether iterator Iter has more vertices to examine
 894
 895       function Iterate_Component_Vertices
 896         (G    : Library_Graph;
 897          Comp : Component_Id) return Component_Vertex_Iterator;
 898       pragma Inline (Iterate_Component_Vertices);
 899       --  Obtain an iterator over all vertices of component Comp of library
 900       --  graph G.
 901
 902       procedure Next
 903         (Iter   : in out Component_Vertex_Iterator;
 904          Vertex : out Library_Graph_Vertex_Id);
 905       pragma Inline (Next);
 906       --  Return the current vertex referenced by iterator Iter and advance
 907       --  to the next available vertex.
 908
 909       --  The following type represents an iterator over all edges that form a
 910       --  cycle.
 911
 912       type Edges_Of_Cycle_Iterator is private;
 913
 914       function Has_Next (Iter : Edges_Of_Cycle_Iterator) return Boolean;
 915       pragma Inline (Has_Next);
 916       --  Determine whether iterator Iter has more edges to examine
 917
 918       function Iterate_Edges_Of_Cycle
 919         (G     : Library_Graph;
 920          Cycle : Library_Graph_Cycle_Id) return Edges_Of_Cycle_Iterator;
 921       pragma Inline (Iterate_Edges_Of_Cycle);
 922       --  Obtain an iterator over all edges that form cycle Cycle of library
 923       --  graph G.
 924
 925       procedure Next
 926         (Iter : in out Edges_Of_Cycle_Iterator;
 927          Edge : out Library_Graph_Edge_Id);
 928       pragma Inline (Next);
 929       --  Return the current edge referenced by iterator Iter and advance to
 930       --  the next available edge.
 931
 932       --  The following type represents an iterator over all edges that reach
 933       --  successors starting from a particular predecessor vertex.
 934
 935       type Edges_To_Successors_Iterator is private;
 936
 937       function Has_Next (Iter : Edges_To_Successors_Iterator) return Boolean;
 938       pragma Inline (Has_Next);
 939       --  Determine whether iterator Iter has more edges to examine
 940
 941       function Iterate_Edges_To_Successors
 942         (G      : Library_Graph;
 943          Vertex : Library_Graph_Vertex_Id) return Edges_To_Successors_Iterator;
 944       pragma Inline (Iterate_Edges_To_Successors);
 945       --  Obtain an iterator over all edges to successors with predecessor
 946       --  vertex Vertex of library graph G.
 947
 948       procedure Next
 949         (Iter : in out Edges_To_Successors_Iterator;
 950          Edge : out Library_Graph_Edge_Id);
 951       pragma Inline (Next);
 952       --  Return the current edge referenced by iterator Iter and advance to
 953       --  the next available edge.
 954
 955    private
 956
 957       --------------
 958       -- Vertices --
 959       --------------
 960
 961       --  The following type represents the attributes of a library graph
 962       --  vertex.
 963
 964       type Library_Graph_Vertex_Attributes is record
 965          Corresponding_Item : Library_Graph_Vertex_Id :=
 966                                 No_Library_Graph_Vertex;
 967          --  The reference to the corresponding spec or body. This attribute is
 968          --  set as follows:
 969          --
 970          --    * If predicate Is_Body_With_Spec is True, the reference denotes
 971          --      the corresponding spec.
 972          --
 973          --    * If predicate Is_Spec_With_Body is True, the reference denotes
 974          --      the corresponding body.
 975          --
 976          --    * Otherwise the attribute remains empty.
 977
 978          In_Elaboration_Order : Boolean := False;
 979          --  Set when this vertex is elaborated
 980
 981          Pending_Strong_Predecessors : Natural := 0;
 982          --  The number of pending strong predecessor vertices this vertex must
 983          --  wait on before it can be elaborated.
 984
 985          Pending_Weak_Predecessors : Natural := 0;
 986          --  The number of weak predecessor vertices this vertex must wait on
 987          --  before it can be elaborated.
 988
 989          Unit : Unit_Id := No_Unit_Id;
 990          --  The reference to unit this vertex represents
 991       end record;
 992
 993       No_Library_Graph_Vertex_Attributes :
 994         constant Library_Graph_Vertex_Attributes :=
 995           (Corresponding_Item          => No_Library_Graph_Vertex,
 996            In_Elaboration_Order        => False,
 997            Pending_Strong_Predecessors => 0,
 998            Pending_Weak_Predecessors   => 0,
 999            Unit                        => No_Unit_Id);
1000
1001       procedure Destroy_Library_Graph_Vertex_Attributes
1002         (Attrs : in out Library_Graph_Vertex_Attributes);
1003       pragma Inline (Destroy_Library_Graph_Vertex_Attributes);
1004       --  Destroy the contents of attributes Attrs
1005
1006       package LGV_Tables is new Dynamic_Hash_Tables
1007         (Key_Type              => Library_Graph_Vertex_Id,
1008          Value_Type            => Library_Graph_Vertex_Attributes,
1009          No_Value              => No_Library_Graph_Vertex_Attributes,
1010          Expansion_Threshold   => 1.5,
1011          Expansion_Factor      => 2,
1012          Compression_Threshold => 0.3,
1013          Compression_Factor    => 2,
1014          "="                   => "=",
1015          Destroy_Value         => Destroy_Library_Graph_Vertex_Attributes,
1016          Hash                  => Hash_Library_Graph_Vertex);
1017
1018       -----------
1019       -- Edges --
1020       -----------
1021
1022       --  The following type represents the attributes of a library graph edge
1023
1024       type Library_Graph_Edge_Attributes is record
1025          Activates_Task : Boolean := False;
1026          --  Set for an invocation edge, where at least one of the paths the
1027          --  edge represents activates a task.
1028
1029          Kind : Library_Graph_Edge_Kind := No_Edge;
1030          --  The nature of the library graph edge
1031       end record;
1032
1033       No_Library_Graph_Edge_Attributes :
1034         constant Library_Graph_Edge_Attributes :=
1035           (Activates_Task => False,
1036            Kind           => No_Edge);
1037
1038       procedure Destroy_Library_Graph_Edge_Attributes
1039         (Attrs : in out Library_Graph_Edge_Attributes);
1040       pragma Inline (Destroy_Library_Graph_Edge_Attributes);
1041       --  Destroy the contents of attributes Attrs
1042
1043       package LGE_Tables is new Dynamic_Hash_Tables
1044         (Key_Type              => Library_Graph_Edge_Id,
1045          Value_Type            => Library_Graph_Edge_Attributes,
1046          No_Value              => No_Library_Graph_Edge_Attributes,
1047          Expansion_Threshold   => 1.5,
1048          Expansion_Factor      => 2,
1049          Compression_Threshold => 0.3,
1050          Compression_Factor    => 2,
1051          "="                   => "=",
1052          Destroy_Value         => Destroy_Library_Graph_Edge_Attributes,
1053          Hash                  => Hash_Library_Graph_Edge);
1054
1055       ----------------
1056       -- Components --
1057       ----------------
1058
1059       --  The following type represents the attributes of a component
1060
1061       type Component_Attributes is record
1062          Pending_Strong_Predecessors : Natural := 0;
1063          --  The number of pending strong predecessor components this component
1064          --  must wait on before it can be elaborated.
1065
1066          Pending_Weak_Predecessors : Natural := 0;
1067          --  The number of pending weak predecessor components this component
1068          --  must wait on before it can be elaborated.
1069       end record;
1070
1071       No_Component_Attributes : constant Component_Attributes :=
1072         (Pending_Strong_Predecessors => 0,
1073          Pending_Weak_Predecessors   => 0);
1074
1075       procedure Destroy_Component_Attributes
1076         (Attrs : in out Component_Attributes);
1077       pragma Inline (Destroy_Component_Attributes);
1078       --  Destroy the contents of attributes Attrs
1079
1080       package Component_Tables is new Dynamic_Hash_Tables
1081         (Key_Type              => Component_Id,
1082          Value_Type            => Component_Attributes,
1083          No_Value              => No_Component_Attributes,
1084          Expansion_Threshold   => 1.5,
1085          Expansion_Factor      => 2,
1086          Compression_Threshold => 0.3,
1087          Compression_Factor    => 2,
1088          "="                   => "=",
1089          Destroy_Value         => Destroy_Component_Attributes,
1090          Hash                  => Hash_Component);
1091
1092       ------------
1093       -- Cycles --
1094       ------------
1095
1096       --  The following type represents the attributes of a cycle
1097
1098       type Library_Graph_Cycle_Attributes is record
1099          Invocation_Edge_Count : Natural := 0;
1100          --  The number of invocation edges within the cycle
1101
1102          Kind : Library_Graph_Cycle_Kind := No_Cycle_Kind;
1103          --  The nature of the cycle
1104
1105          Path : LGE_Lists.Doubly_Linked_List := LGE_Lists.Nil;
1106          --  The path of edges that form the cycle
1107       end record;
1108
1109       No_Library_Graph_Cycle_Attributes :
1110         constant Library_Graph_Cycle_Attributes :=
1111           (Invocation_Edge_Count => 0,
1112            Kind                  => No_Cycle_Kind,
1113            Path                  => LGE_Lists.Nil);
1114
1115       procedure Destroy_Library_Graph_Cycle_Attributes
1116         (Attrs : in out Library_Graph_Cycle_Attributes);
1117       pragma Inline (Destroy_Library_Graph_Cycle_Attributes);
1118       --  Destroy the contents of attributes Attrs
1119
1120       function Hash_Library_Graph_Cycle_Attributes
1121         (Attrs : Library_Graph_Cycle_Attributes) return Bucket_Range_Type;
1122       pragma Inline (Hash_Library_Graph_Cycle_Attributes);
1123       --  Obtain the hash of key Attrs
1124
1125       function Same_Library_Graph_Cycle_Attributes
1126         (Left  : Library_Graph_Cycle_Attributes;
1127          Right : Library_Graph_Cycle_Attributes) return Boolean;
1128       pragma Inline (Same_Library_Graph_Cycle_Attributes);
1129       --  Determine whether cycle attributes Left and Right are the same
1130
1131       package LGC_Tables is new Dynamic_Hash_Tables
1132         (Key_Type              => Library_Graph_Cycle_Id,
1133          Value_Type            => Library_Graph_Cycle_Attributes,
1134          No_Value              => No_Library_Graph_Cycle_Attributes,
1135          Expansion_Threshold   => 1.5,
1136          Expansion_Factor      => 2,
1137          Compression_Threshold => 0.3,
1138          Compression_Factor    => 2,
1139          "="                   => "=",
1140          Destroy_Value         => Destroy_Library_Graph_Cycle_Attributes,
1141          Hash                  => Hash_Library_Graph_Cycle);
1142
1143       --------------------
1144       -- Recorded edges --
1145       --------------------
1146
1147       --  The following type represents a relation between a predecessor and
1148       --  successor vertices.
1149
1150       type Predecessor_Successor_Relation is record
1151          Predecessor : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
1152          --  The source vertex
1153
1154          Successor : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
1155          --  The destination vertex
1156       end record;
1157
1158       No_Predecessor_Successor_Relation :
1159         constant Predecessor_Successor_Relation :=
1160           (Predecessor => No_Library_Graph_Vertex,
1161            Successor   => No_Library_Graph_Vertex);
1162
1163       function Hash_Predecessor_Successor_Relation
1164         (Rel : Predecessor_Successor_Relation) return Bucket_Range_Type;
1165       pragma Inline (Hash_Predecessor_Successor_Relation);
1166       --  Obtain the hash value of key Rel
1167
1168       package RE_Sets is new Membership_Sets
1169         (Element_Type => Predecessor_Successor_Relation,
1170          "="          => "=",
1171          Hash         => Hash_Predecessor_Successor_Relation);
1172
1173       ----------------
1174       -- Statistics --
1175       ----------------
1176
1177       type Library_Graph_Edge_Counts is
1178         array (Library_Graph_Edge_Kind) of Natural;
1179
1180       -----------
1181       -- Units --
1182       -----------
1183
1184       package Unit_Tables is new Dynamic_Hash_Tables
1185         (Key_Type              => Unit_Id,
1186          Value_Type            => Library_Graph_Vertex_Id,
1187          No_Value              => No_Library_Graph_Vertex,
1188          Expansion_Threshold   => 1.5,
1189          Expansion_Factor      => 2,
1190          Compression_Threshold => 0.3,
1191          Compression_Factor    => 2,
1192          "="                   => "=",
1193          Destroy_Value         => Destroy_Library_Graph_Vertex,
1194          Hash                  => Hash_Unit);
1195
1196       -----------
1197       -- Graph --
1198       -----------
1199
1200       package DG is new Directed_Graphs
1201         (Vertex_Id   => Library_Graph_Vertex_Id,
1202          No_Vertex   => No_Library_Graph_Vertex,
1203          Hash_Vertex => Hash_Library_Graph_Vertex,
1204          Same_Vertex => "=",
1205          Edge_Id     => Library_Graph_Edge_Id,
1206          No_Edge     => No_Library_Graph_Edge,
1207          Hash_Edge   => Hash_Library_Graph_Edge,
1208          Same_Edge   => "=");
1209
1210       --  The following type represents the attributes of a library graph
1211
1212       type Library_Graph_Attributes is record
1213          Component_Attributes : Component_Tables.Dynamic_Hash_Table :=
1214                                   Component_Tables.Nil;
1215          --  The map of component -> component attributes for all components in
1216          --  the graph.
1217
1218          Counts : Library_Graph_Edge_Counts := (others => 0);
1219          --  Edge statistics
1220
1221          Cycle_Attributes : LGC_Tables.Dynamic_Hash_Table := LGC_Tables.Nil;
1222          --  The map of cycle -> cycle attributes for all cycles in the graph
1223
1224          Cycles : LGC_Lists.Doubly_Linked_List := LGC_Lists.Nil;
1225          --  The list of all cycles in the graph, sorted based on precedence
1226
1227          Edge_Attributes : LGE_Tables.Dynamic_Hash_Table := LGE_Tables.Nil;
1228          --  The map of edge -> edge attributes for all edges in the graph
1229
1230          Graph : DG.Directed_Graph := DG.Nil;
1231          --  The underlying graph describing the relations between edges and
1232          --  vertices.
1233
1234          Recorded_Edges : RE_Sets.Membership_Set := RE_Sets.Nil;
1235          --  The set of recorded edges, used to prevent duplicate edges in the
1236          --  graph.
1237
1238          Unit_To_Vertex : Unit_Tables.Dynamic_Hash_Table := Unit_Tables.Nil;
1239          --  The map of unit -> vertex
1240
1241          Vertex_Attributes : LGV_Tables.Dynamic_Hash_Table := LGV_Tables.Nil;
1242          --  The map of vertex -> vertex attributes for all vertices in the
1243          --  graph.
1244       end record;
1245
1246       type Library_Graph is access Library_Graph_Attributes;
1247       Nil : constant Library_Graph := null;
1248
1249       ---------------
1250       -- Iterators --
1251       ---------------
1252
1253       type All_Cycle_Iterator           is new LGC_Lists.Iterator;
1254       type All_Edge_Iterator            is new DG.All_Edge_Iterator;
1255       type All_Vertex_Iterator          is new DG.All_Vertex_Iterator;
1256       type Component_Iterator           is new DG.Component_Iterator;
1257       type Component_Vertex_Iterator    is new DG.Component_Vertex_Iterator;
1258       type Edges_Of_Cycle_Iterator      is new LGE_Lists.Iterator;
1259       type Edges_To_Successors_Iterator is new DG.Outgoing_Edge_Iterator;
1260    end Library_Graphs;
1261
1262    -----------------------
1263    -- Invocation_Graphs --
1264    -----------------------
1265
1266    package Invocation_Graphs is
1267
1268       -----------
1269       -- Graph --
1270       -----------
1271
1272       --  The following type denotes an invocation graph handle. Each instance
1273       --  must be created using routine Create.
1274
1275       type Invocation_Graph is private;
1276       Nil : constant Invocation_Graph;
1277
1278       ----------------------
1279       -- Graph operations --
1280       ----------------------
1281
1282       procedure Add_Edge
1283         (G      : Invocation_Graph;
1284          Source : Invocation_Graph_Vertex_Id;
1285          Target : Invocation_Graph_Vertex_Id;
1286          IR_Id  : Invocation_Relation_Id);
1287       pragma Inline (Add_Edge);
1288       --  Create a new edge in invocation graph G with source vertex Source and
1289       --  destination vertex Target. IR_Id is the invocation relation the edge
1290       --  describes.
1291
1292       procedure Add_Vertex
1293         (G           : Invocation_Graph;
1294          IC_Id       : Invocation_Construct_Id;
1295          Body_Vertex : Library_Graph_Vertex_Id;
1296          Spec_Vertex : Library_Graph_Vertex_Id);
1297       pragma Inline (Add_Vertex);
1298       --  Create a new vertex in invocation graph G. IC_Id is the invocation
1299       --  construct the vertex describes. Body_Vertex denotes the library graph
1300       --  vertex where the invocation construct's body is declared. Spec_Vertex
1301       --  is the library graph vertex where the invocation construct's spec is
1302       --  declared.
1303
1304       function Create
1305         (Initial_Vertices : Positive;
1306          Initial_Edges    : Positive;
1307          Lib_Graph        : Library_Graphs.Library_Graph)
1308         return Invocation_Graph;
1309       pragma Inline (Create);
1310       --  Create a new empty graph with vertex capacity Initial_Vertices
1311       --  and edge capacity Initial_Edges. Lib_Graph is the library graph
1312       --  corresponding to this invocation graph.
1313
1314       function Get_Lib_Graph
1315         (G : Invocation_Graph) return Library_Graphs.Library_Graph;
1316       pragma Inline (Get_Lib_Graph);
1317       --  Return the library graph corresponding to this invocation graph
1318
1319       procedure Destroy (G : in out Invocation_Graph);
1320       pragma Inline (Destroy);
1321       --  Destroy the contents of invocation graph G, rendering it unusable
1322
1323       function Present (G : Invocation_Graph) return Boolean;
1324       pragma Inline (Present);
1325       --  Determine whether invocation graph G exists
1326
1327       -----------------------
1328       -- Vertex attributes --
1329       -----------------------
1330
1331       function Body_Vertex
1332         (G      : Invocation_Graph;
1333          Vertex : Invocation_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
1334       pragma Inline (Body_Vertex);
1335       --  Obtain the library graph vertex where the body of the invocation
1336       --  construct represented by vertex Vertex of invocation graph G is
1337       --  declared.
1338
1339       function Column
1340         (G      : Invocation_Graph;
1341          Vertex : Invocation_Graph_Vertex_Id) return Nat;
1342       pragma Inline (Column);
1343       --  Obtain the column number where the invocation construct vertex Vertex
1344       --  of invocation graph G describes.
1345
1346       function Construct
1347         (G      : Invocation_Graph;
1348          Vertex : Invocation_Graph_Vertex_Id) return Invocation_Construct_Id;
1349       pragma Inline (Construct);
1350       --  Obtain the invocation construct vertex Vertex of invocation graph G
1351       --  describes.
1352
1353       function Corresponding_Vertex
1354         (G     : Invocation_Graph;
1355          IS_Id : Invocation_Signature_Id) return Invocation_Graph_Vertex_Id;
1356       pragma Inline (Corresponding_Vertex);
1357       --  Obtain the vertex of invocation graph G that corresponds to signature
1358       --  IS_Id.
1359
1360       function Line
1361         (G      : Invocation_Graph;
1362          Vertex : Invocation_Graph_Vertex_Id) return Nat;
1363       pragma Inline (Line);
1364       --  Obtain the line number where the invocation construct vertex Vertex
1365       --  of invocation graph G describes.
1366
1367       function Name
1368         (G      : Invocation_Graph;
1369          Vertex : Invocation_Graph_Vertex_Id) return Name_Id;
1370       pragma Inline (Name);
1371       --  Obtain the name of the construct vertex Vertex of invocation graph G
1372       --  describes.
1373
1374       function Spec_Vertex
1375         (G      : Invocation_Graph;
1376          Vertex : Invocation_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
1377       pragma Inline (Spec_Vertex);
1378       --  Obtain the library graph vertex where the spec of the invocation
1379       --  construct represented by vertex Vertex of invocation graph G is
1380       --  declared.
1381
1382       ---------------------
1383       -- Edge attributes --
1384       ---------------------
1385
1386       function Extra
1387         (G    : Invocation_Graph;
1388          Edge : Invocation_Graph_Edge_Id) return Name_Id;
1389       pragma Inline (Extra);
1390       --  Obtain the extra name used in error diagnostics of edge Edge of
1391       --  invocation graph G.
1392
1393       function Kind
1394         (G    : Invocation_Graph;
1395          Edge : Invocation_Graph_Edge_Id) return Invocation_Kind;
1396       pragma Inline (Kind);
1397       --  Obtain the nature of edge Edge of invocation graph G
1398
1399       function Relation
1400         (G    : Invocation_Graph;
1401          Edge : Invocation_Graph_Edge_Id) return Invocation_Relation_Id;
1402       pragma Inline (Relation);
1403       --  Obtain the relation edge Edge of invocation graph G describes
1404
1405       function Target
1406         (G    : Invocation_Graph;
1407          Edge : Invocation_Graph_Edge_Id) return Invocation_Graph_Vertex_Id;
1408       pragma Inline (Target);
1409       --  Obtain the target vertex edge Edge of invocation graph G designates
1410
1411       ----------------
1412       -- Statistics --
1413       ----------------
1414
1415       function Invocation_Graph_Edge_Count
1416         (G    : Invocation_Graph;
1417          Kind : Invocation_Kind) return Natural;
1418       pragma Inline (Invocation_Graph_Edge_Count);
1419       --  Obtain the total number of edges of kind Kind in invocation graph G
1420
1421       function Number_Of_Edges (G : Invocation_Graph) return Natural;
1422       pragma Inline (Number_Of_Edges);
1423       --  Obtain the total number of edges in invocation graph G
1424
1425       function Number_Of_Edges_To_Targets
1426         (G      : Invocation_Graph;
1427          Vertex : Invocation_Graph_Vertex_Id) return Natural;
1428       pragma Inline (Number_Of_Edges_To_Targets);
1429       --  Obtain the total number of edges to targets vertex Vertex of
1430       --  invocation graph G has.
1431
1432       function Number_Of_Elaboration_Roots
1433         (G : Invocation_Graph) return Natural;
1434       pragma Inline (Number_Of_Elaboration_Roots);
1435       --  Obtain the total number of elaboration roots in invocation graph G
1436
1437       function Number_Of_Vertices (G : Invocation_Graph) return Natural;
1438       pragma Inline (Number_Of_Vertices);
1439       --  Obtain the total number of vertices in invocation graph G
1440
1441       ---------------
1442       -- Iterators --
1443       ---------------
1444
1445       --  The following type represents an iterator over all edges of an
1446       --  invocation graph.
1447
1448       type All_Edge_Iterator is private;
1449
1450       function Has_Next (Iter : All_Edge_Iterator) return Boolean;
1451       pragma Inline (Has_Next);
1452       --  Determine whether iterator Iter has more edges to examine
1453
1454       function Iterate_All_Edges
1455         (G : Invocation_Graph) return All_Edge_Iterator;
1456       pragma Inline (Iterate_All_Edges);
1457       --  Obtain an iterator over all edges of invocation graph G
1458
1459       procedure Next
1460         (Iter : in out All_Edge_Iterator;
1461          Edge : out Invocation_Graph_Edge_Id);
1462       pragma Inline (Next);
1463       --  Return the current edge referenced by iterator Iter and advance to
1464       --  the next available edge.
1465
1466       --  The following type represents an iterator over all vertices of an
1467       --  invocation graph.
1468
1469       type All_Vertex_Iterator is private;
1470
1471       function Has_Next (Iter : All_Vertex_Iterator) return Boolean;
1472       pragma Inline (Has_Next);
1473       --  Determine whether iterator Iter has more vertices to examine
1474
1475       function Iterate_All_Vertices
1476         (G : Invocation_Graph) return All_Vertex_Iterator;
1477       pragma Inline (Iterate_All_Vertices);
1478       --  Obtain an iterator over all vertices of invocation graph G
1479
1480       procedure Next
1481         (Iter   : in out All_Vertex_Iterator;
1482          Vertex : out Invocation_Graph_Vertex_Id);
1483       pragma Inline (Next);
1484       --  Return the current vertex referenced by iterator Iter and advance
1485       --  to the next available vertex.
1486
1487       --  The following type represents an iterator over all edges that reach
1488       --  targets starting from a particular source vertex.
1489
1490       type Edges_To_Targets_Iterator is private;
1491
1492       function Has_Next (Iter : Edges_To_Targets_Iterator) return Boolean;
1493       pragma Inline (Has_Next);
1494       --  Determine whether iterator Iter has more edges to examine
1495
1496       function Iterate_Edges_To_Targets
1497         (G      : Invocation_Graph;
1498          Vertex : Invocation_Graph_Vertex_Id) return Edges_To_Targets_Iterator;
1499       pragma Inline (Iterate_Edges_To_Targets);
1500       --  Obtain an iterator over all edges to targets with source vertex
1501       --  Vertex of invocation graph G.
1502
1503       procedure Next
1504         (Iter : in out Edges_To_Targets_Iterator;
1505          Edge : out Invocation_Graph_Edge_Id);
1506       pragma Inline (Next);
1507       --  Return the current edge referenced by iterator Iter and advance to
1508       --  the next available edge.
1509
1510       --  The following type represents an iterator over all vertices of an
1511       --  invocation graph that denote the elaboration procedure or a spec or
1512       --  a body, referred to as elaboration root.
1513
1514       type Elaboration_Root_Iterator is private;
1515
1516       function Has_Next (Iter : Elaboration_Root_Iterator) return Boolean;
1517       pragma Inline (Has_Next);
1518       --  Determine whether iterator Iter has more elaboration roots to examine
1519
1520       function Iterate_Elaboration_Roots
1521         (G : Invocation_Graph) return Elaboration_Root_Iterator;
1522       pragma Inline (Iterate_Elaboration_Roots);
1523       --  Obtain an iterator over all elaboration roots of invocation graph G
1524
1525       procedure Next
1526         (Iter : in out Elaboration_Root_Iterator;
1527          Root : out Invocation_Graph_Vertex_Id);
1528       pragma Inline (Next);
1529       --  Return the current elaboration root referenced by iterator Iter and
1530       --  advance to the next available elaboration root.
1531
1532    private
1533
1534       --------------
1535       -- Vertices --
1536       --------------
1537
1538       procedure Destroy_Invocation_Graph_Vertex
1539         (Vertex : in out Invocation_Graph_Vertex_Id);
1540       pragma Inline (Destroy_Invocation_Graph_Vertex);
1541       --  Destroy invocation graph vertex Vertex
1542
1543       --  The following type represents the attributes of an invocation graph
1544       --  vertex.
1545
1546       type Invocation_Graph_Vertex_Attributes is record
1547          Body_Vertex : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
1548          --  Reference to the library graph vertex where the body of this
1549          --  vertex resides.
1550
1551          Construct : Invocation_Construct_Id := No_Invocation_Construct;
1552          --  Reference to the invocation construct this vertex represents
1553
1554          Spec_Vertex : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
1555          --  Reference to the library graph vertex where the spec of this
1556          --  vertex resides.
1557       end record;
1558
1559       No_Invocation_Graph_Vertex_Attributes :
1560         constant Invocation_Graph_Vertex_Attributes :=
1561           (Body_Vertex => No_Library_Graph_Vertex,
1562            Construct   => No_Invocation_Construct,
1563            Spec_Vertex => No_Library_Graph_Vertex);
1564
1565       procedure Destroy_Invocation_Graph_Vertex_Attributes
1566         (Attrs : in out Invocation_Graph_Vertex_Attributes);
1567       pragma Inline (Destroy_Invocation_Graph_Vertex_Attributes);
1568       --  Destroy the contents of attributes Attrs
1569
1570       package IGV_Tables is new Dynamic_Hash_Tables
1571         (Key_Type              => Invocation_Graph_Vertex_Id,
1572          Value_Type            => Invocation_Graph_Vertex_Attributes,
1573          No_Value              => No_Invocation_Graph_Vertex_Attributes,
1574          Expansion_Threshold   => 1.5,
1575          Expansion_Factor      => 2,
1576          Compression_Threshold => 0.3,
1577          Compression_Factor    => 2,
1578          "="                   => "=",
1579          Destroy_Value         => Destroy_Invocation_Graph_Vertex_Attributes,
1580          Hash                  => Hash_Invocation_Graph_Vertex);
1581
1582       -----------
1583       -- Edges --
1584       -----------
1585
1586       procedure Destroy_Invocation_Graph_Edge
1587         (Edge : in out Invocation_Graph_Edge_Id);
1588       pragma Inline (Destroy_Invocation_Graph_Edge);
1589       --  Destroy invocation graph edge Edge
1590
1591       --  The following type represents the attributes of an invocation graph
1592       --  edge.
1593
1594       type Invocation_Graph_Edge_Attributes is record
1595          Relation : Invocation_Relation_Id := No_Invocation_Relation;
1596          --  Reference to the invocation relation this edge represents
1597       end record;
1598
1599       No_Invocation_Graph_Edge_Attributes :
1600         constant Invocation_Graph_Edge_Attributes :=
1601           (Relation => No_Invocation_Relation);
1602
1603       procedure Destroy_Invocation_Graph_Edge_Attributes
1604         (Attrs : in out Invocation_Graph_Edge_Attributes);
1605       pragma Inline (Destroy_Invocation_Graph_Edge_Attributes);
1606       --  Destroy the contents of attributes Attrs
1607
1608       package IGE_Tables is new Dynamic_Hash_Tables
1609         (Key_Type              => Invocation_Graph_Edge_Id,
1610          Value_Type            => Invocation_Graph_Edge_Attributes,
1611          No_Value              => No_Invocation_Graph_Edge_Attributes,
1612          Expansion_Threshold   => 1.5,
1613          Expansion_Factor      => 2,
1614          Compression_Threshold => 0.3,
1615          Compression_Factor    => 2,
1616          "="                   => "=",
1617          Destroy_Value         => Destroy_Invocation_Graph_Edge_Attributes,
1618          Hash                  => Hash_Invocation_Graph_Edge);
1619
1620       ---------------
1621       -- Relations --
1622       ---------------
1623
1624       --  The following type represents a relation between a source and target
1625       --  vertices.
1626
1627       type Source_Target_Relation is record
1628          Source : Invocation_Graph_Vertex_Id := No_Invocation_Graph_Vertex;
1629          --  The source vertex
1630
1631          Target : Invocation_Graph_Vertex_Id := No_Invocation_Graph_Vertex;
1632          --  The destination vertex
1633       end record;
1634
1635       No_Source_Target_Relation :
1636         constant Source_Target_Relation :=
1637           (Source => No_Invocation_Graph_Vertex,
1638            Target => No_Invocation_Graph_Vertex);
1639
1640       function Hash_Source_Target_Relation
1641         (Rel : Source_Target_Relation) return Bucket_Range_Type;
1642       pragma Inline (Hash_Source_Target_Relation);
1643       --  Obtain the hash value of key Rel
1644
1645       package Relation_Sets is new Membership_Sets
1646         (Element_Type => Source_Target_Relation,
1647          "="          => "=",
1648          Hash         => Hash_Source_Target_Relation);
1649
1650       ----------------
1651       -- Statistics --
1652       ----------------
1653
1654       type Invocation_Graph_Edge_Counts is array (Invocation_Kind) of Natural;
1655
1656       ----------------
1657       -- Signatures --
1658       ----------------
1659
1660       function Hash_Invocation_Signature
1661         (IS_Id : Invocation_Signature_Id) return Bucket_Range_Type;
1662       pragma Inline (Hash_Invocation_Signature);
1663       --  Obtain the hash value of key IS_Id
1664
1665       package Signature_Tables is new Dynamic_Hash_Tables
1666         (Key_Type              => Invocation_Signature_Id,
1667          Value_Type            => Invocation_Graph_Vertex_Id,
1668          No_Value              => No_Invocation_Graph_Vertex,
1669          Expansion_Threshold   => 1.5,
1670          Expansion_Factor      => 2,
1671          Compression_Threshold => 0.3,
1672          Compression_Factor    => 2,
1673          "="                   => "=",
1674          Destroy_Value         => Destroy_Invocation_Graph_Vertex,
1675          Hash                  => Hash_Invocation_Signature);
1676
1677       -----------------------
1678       -- Elaboration roots --
1679       -----------------------
1680
1681       package IGV_Sets is new Membership_Sets
1682         (Element_Type => Invocation_Graph_Vertex_Id,
1683          "="          => "=",
1684          Hash         => Hash_Invocation_Graph_Vertex);
1685
1686       -----------
1687       -- Graph --
1688       -----------
1689
1690       package DG is new Directed_Graphs
1691         (Vertex_Id   => Invocation_Graph_Vertex_Id,
1692          No_Vertex   => No_Invocation_Graph_Vertex,
1693          Hash_Vertex => Hash_Invocation_Graph_Vertex,
1694          Same_Vertex => "=",
1695          Edge_id     => Invocation_Graph_Edge_Id,
1696          No_Edge     => No_Invocation_Graph_Edge,
1697          Hash_Edge   => Hash_Invocation_Graph_Edge,
1698          Same_Edge   => "=");
1699
1700       --  The following type represents the attributes of an invocation graph
1701
1702       type Invocation_Graph_Attributes is record
1703          Counts : Invocation_Graph_Edge_Counts := (others => 0);
1704          --  Edge statistics
1705
1706          Edge_Attributes : IGE_Tables.Dynamic_Hash_Table := IGE_Tables.Nil;
1707          --  The map of edge -> edge attributes for all edges in the graph
1708
1709          Graph : DG.Directed_Graph := DG.Nil;
1710          --  The underlying graph describing the relations between edges and
1711          --  vertices.
1712
1713          Relations : Relation_Sets.Membership_Set := Relation_Sets.Nil;
1714          --  The set of relations between source and targets, used to prevent
1715          --  duplicate edges in the graph.
1716
1717          Roots : IGV_Sets.Membership_Set := IGV_Sets.Nil;
1718          --  The set of elaboration root vertices
1719
1720          Signature_To_Vertex : Signature_Tables.Dynamic_Hash_Table :=
1721                                  Signature_Tables.Nil;
1722          --  The map of signature -> vertex
1723
1724          Vertex_Attributes : IGV_Tables.Dynamic_Hash_Table := IGV_Tables.Nil;
1725          --  The map of vertex -> vertex attributes for all vertices in the
1726          --  graph.
1727
1728          Lib_Graph : Library_Graphs.Library_Graph;
1729       end record;
1730
1731       type Invocation_Graph is access Invocation_Graph_Attributes;
1732       Nil : constant Invocation_Graph := null;
1733
1734       ---------------
1735       -- Iterators --
1736       ---------------
1737
1738       type All_Edge_Iterator         is new DG.All_Edge_Iterator;
1739       type All_Vertex_Iterator       is new DG.All_Vertex_Iterator;
1740       type Edges_To_Targets_Iterator is new DG.Outgoing_Edge_Iterator;
1741       type Elaboration_Root_Iterator is new IGV_Sets.Iterator;
1742    end Invocation_Graphs;
1743
1744 end Bindo.Graphs;