gcc/ada/bindo-elaborators.adb

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT COMPILER COMPONENTS                         --
   4 --                                                                          --
   5 --                     B I N D O . E L A B O R A T O R S                    --
   6 --                                                                          --
   7 --                                 B o d y                                  --
   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 with Butil;  use Butil;
  27 with Debug;  use Debug;
  28 with Output; use Output;
  29 with Types;  use Types;
  30
  31 with Bindo.Augmentors;
  32 use  Bindo.Augmentors;
  33 use  Bindo.Augmentors.Library_Graph_Augmentors;
  34
  35 with Bindo.Builders;
  36 use  Bindo.Builders;
  37 use  Bindo.Builders.Invocation_Graph_Builders;
  38 use  Bindo.Builders.Library_Graph_Builders;
  39
  40 with Bindo.Diagnostics;
  41 use  Bindo.Diagnostics;
  42
  43 with Bindo.Units;
  44 use  Bindo.Units;
  45
  46 with Bindo.Validators;
  47 use  Bindo.Validators;
  48 use  Bindo.Validators.Elaboration_Order_Validators;
  49
  50 with Bindo.Writers;
  51 use  Bindo.Writers;
  52 use  Bindo.Writers.ALI_Writers;
  53 use  Bindo.Writers.Dependency_Writers;
  54 use  Bindo.Writers.Elaboration_Order_Writers;
  55 use  Bindo.Writers.Invocation_Graph_Writers;
  56 use  Bindo.Writers.Library_Graph_Writers;
  57 use  Bindo.Writers.Phase_Writers;
  58 use  Bindo.Writers.Unit_Closure_Writers;
  59
  60 with GNAT;        use GNAT;
  61 with GNAT.Graphs; use GNAT.Graphs;
  62
  63 package body Bindo.Elaborators is
  64
  65    --  The following type defines the advancement of the elaboration order
  66    --  algorithm in terms of steps.
  67
  68    type Elaboration_Order_Step is new Natural;
  69
  70    Initial_Step : constant Elaboration_Order_Step :=
  71                     Elaboration_Order_Step'First;
  72
  73    ----------------------------------------------
  74    -- Invocation_And_Library_Graph_Elaborators --
  75    ----------------------------------------------
  76
  77    package body Invocation_And_Library_Graph_Elaborators is
  78
  79       -----------------------
  80       -- Local subprograms --
  81       -----------------------
  82
  83       procedure Create_Component_Vertex_Sets
  84         (G                   : Library_Graph;
  85          Comp                : Component_Id;
  86          Elaborable_Vertices : out LGV_Sets.Membership_Set;
  87          Waiting_Vertices    : out LGV_Sets.Membership_Set;
  88          Step                : Elaboration_Order_Step);
  89       pragma Inline (Create_Component_Vertex_Sets);
  90       --  Split all vertices of component Comp of library graph G as follows:
  91       --
  92       --    * Elaborable vertices are added to set Elaborable_Vertices.
  93       --
  94       --    * Vertices that are still waiting on their predecessors to be
  95       --      elaborated are added to set Waiting_Vertices.
  96       --
  97       --  Step is the current step in the elaboration order.
  98
  99       procedure Create_Vertex_Sets
 100         (G                   : Library_Graph;
 101          Elaborable_Vertices : out LGV_Sets.Membership_Set;
 102          Waiting_Vertices    : out LGV_Sets.Membership_Set;
 103          Step                : Elaboration_Order_Step);
 104       pragma Inline (Create_Vertex_Sets);
 105       --  Split all vertices of library graph G as follows:
 106       --
 107       --    * Elaborable vertices are added to set Elaborable_Vertices.
 108       --
 109       --    * Vertices that are still waiting on their predecessors to be
 110       --      elaborated are added to set Waiting_Vertices.
 111       --
 112       --  Step is the current step in the elaboration order.
 113
 114       procedure Elaborate_Component
 115         (G                       : Library_Graph;
 116          Comp                    : Component_Id;
 117          All_Elaborable_Vertices : LGV_Sets.Membership_Set;
 118          All_Waiting_Vertices    : LGV_Sets.Membership_Set;
 119          Order                   : in out Unit_Id_Table;
 120          Step                    : Elaboration_Order_Step);
 121       pragma Inline (Elaborate_Component);
 122       --  Elaborate as many vertices as possible that appear in component Comp
 123       --  of library graph G. The sets contain vertices arranged as follows:
 124       --
 125       --    * All_Elaborable_Vertices - all elaborable vertices in the library
 126       --      graph.
 127       --
 128       --    * All_Waiting_Vertices - all vertices in the library graph that are
 129       --      waiting on predecessors to be elaborated.
 130       --
 131       --  Order is the elaboration order. Step denotes the current step in the
 132       --  elaboration order.
 133
 134       procedure Elaborate_Library_Graph
 135         (G      : Library_Graph;
 136          Order  : out Unit_Id_Table;
 137          Status : out Elaboration_Order_Status);
 138       pragma Inline (Elaborate_Library_Graph);
 139       --  Elaborate as many vertices as possible of library graph G. Order is
 140       --  the elaboration order. Status is the condition of the elaboration
 141       --  order.
 142
 143       procedure Elaborate_Vertex
 144         (G                        : Library_Graph;
 145          Vertex                   : Library_Graph_Vertex_Id;
 146          All_Elaborable_Vertices  : LGV_Sets.Membership_Set;
 147          All_Waiting_Vertices     : LGV_Sets.Membership_Set;
 148          Comp_Elaborable_Vertices : LGV_Sets.Membership_Set;
 149          Comp_Waiting_Vertices    : LGV_Sets.Membership_Set;
 150          Order                    : in out Unit_Id_Table;
 151          Step                     : Elaboration_Order_Step;
 152          Indent                   : Indentation_Level);
 153       pragma Inline (Elaborate_Vertex);
 154       --  Elaborate vertex Vertex of library graph G by adding its unit to
 155       --  elaboration order Order. The routine updates awaiting successors
 156       --  where applicable. The sets contain vertices arranged as follows:
 157       --
 158       --    * All_Elaborable_Vertices - all elaborable vertices in the library
 159       --      graph.
 160       --
 161       --    * All_Waiting_Vertices - all vertices in the library graph that are
 162       --      waiting on predecessors to be elaborated.
 163       --
 164       --    * Comp_Elaborable_Vertices - all elaborable vertices found in the
 165       --      component of Vertex.
 166       --
 167       --    * Comp_Waiting_Vertices - all vertices found in the component of
 168       --      Vertex that are still waiting on predecessors to be elaborated.
 169       --
 170       --  Order denotes the elaboration order. Step is the current step in the
 171       --  elaboration order. Indent denotes the desired indentation level for
 172       --  tracing.
 173
 174       function Find_Best_Elaborable_Vertex
 175         (G      : Library_Graph;
 176          Set    : LGV_Sets.Membership_Set;
 177          Step   : Elaboration_Order_Step;
 178          Indent : Indentation_Level) return Library_Graph_Vertex_Id;
 179       pragma Inline (Find_Best_Elaborable_Vertex);
 180       --  Find the best vertex of library graph G from membership set S that
 181       --  can be elaborated. Step is the current step in the elaboration order.
 182       --  Indent is the desired indentation level for tracing.
 183
 184       function Find_Best_Vertex
 185         (G                   : Library_Graph;
 186          Set                 : LGV_Sets.Membership_Set;
 187          Is_Suitable_Vertex  : LGV_Predicate_Ptr;
 188          Compare_Vertices    : LGV_Comparator_Ptr;
 189          Initial_Best_Msg    : String;
 190          Subsequent_Best_Msg : String;
 191          Step                : Elaboration_Order_Step;
 192          Indent              : Indentation_Level)
 193          return Library_Graph_Vertex_Id;
 194       pragma Inline (Find_Best_Vertex);
 195       --  Find the best vertex of library graph G from membership set S which
 196       --  satisfies predicate Is_Suitable_Vertex and is preferred by comparator
 197       --  Compare_Vertices. Initial_Best_Msg is emitted on the first candidate
 198       --  vertex. Subsequent_Best_Msg is emitted whenever a better vertex is
 199       --  discovered. Step is the current step in the elaboration order. Indent
 200       --  is the desired indentation level for tracing.
 201
 202       function Find_Best_Weakly_Elaborable_Vertex
 203         (G      : Library_Graph;
 204          Set    : LGV_Sets.Membership_Set;
 205          Step   : Elaboration_Order_Step;
 206          Indent : Indentation_Level) return Library_Graph_Vertex_Id;
 207       pragma Inline (Find_Best_Weakly_Elaborable_Vertex);
 208       --  Find the best vertex of library graph G from membership set S that
 209       --  can be weakly elaborated. Step is the current step in the elaboration
 210       --  order. Indent is the desired indentation level for tracing.
 211
 212       function Has_Elaborable_Body
 213         (G      : Library_Graph;
 214          Vertex : Library_Graph_Vertex_Id) return Boolean;
 215       pragma Inline (Has_Elaborable_Body);
 216       --  Determine whether vertex Vertex of library graph G has a body that is
 217       --  elaborable. It is assumed that the vertex has been elaborated.
 218
 219       procedure Insert_Elaborable_Successor
 220         (G                     : Library_Graph;
 221          Vertex                : Library_Graph_Vertex_Id;
 222          Elaborable_Vertices   : LGV_Sets.Membership_Set;
 223          All_Waiting_Vertices  : LGV_Sets.Membership_Set;
 224          Comp_Waiting_Vertices : LGV_Sets.Membership_Set;
 225          Msg                   : String;
 226          Step                  : Elaboration_Order_Step;
 227          Indent                : Indentation_Level);
 228       pragma Inline (Insert_Elaborable_Successor);
 229       --  Add elaborable successor Vertex of library graph G to membership set
 230       --  Elaborable_Vertices and remove it from both All_Waiting_Vertices and
 231       --  Comp_Waiting_Vertices. Msg is a message emitted for tracing purposes.
 232       --  Step is the current step in the elaboration order. Indent denotes the
 233       --  desired indentation level for tracing.
 234
 235       procedure Insert_Vertex
 236         (G      : Library_Graph;
 237          Vertex : Library_Graph_Vertex_Id;
 238          Set    : LGV_Sets.Membership_Set;
 239          Msg    : String;
 240          Step   : Elaboration_Order_Step;
 241          Indent : Indentation_Level);
 242       pragma Inline (Insert_Vertex);
 243       --  Add vertex Vertex of library graph G to membership set Set. Msg is
 244       --  a message emitted for tracing purposes. Step is the current step in
 245       --  the elaboration order. Indent is the desired indentation level for
 246       --  tracing.
 247
 248       function Is_Better_Elaborable_Vertex
 249         (G           : Library_Graph;
 250          Vertex      : Library_Graph_Vertex_Id;
 251          Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind;
 252       pragma Inline (Is_Better_Elaborable_Vertex);
 253       --  Determine whether vertex Vertex of library graph G is a better choice
 254       --  for elaboration compared to vertex Compared_To.
 255
 256       function Is_Better_Weakly_Elaborable_Vertex
 257         (G           : Library_Graph;
 258          Vertex      : Library_Graph_Vertex_Id;
 259          Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind;
 260       pragma Inline (Is_Better_Weakly_Elaborable_Vertex);
 261       --  Determine whether vertex Vertex of library graph G is a better choice
 262       --  for weak elaboration compared to vertex Compared_To.
 263
 264       function Is_Suitable_Elaborable_Vertex
 265         (G      : Library_Graph;
 266          Vertex : Library_Graph_Vertex_Id) return Boolean;
 267       pragma Inline (Is_Suitable_Elaborable_Vertex);
 268       --  Determine whether vertex Vertex of library graph G is suitable for
 269       --  elaboration.
 270
 271       function Is_Suitable_Weakly_Elaborable_Vertex
 272         (G      : Library_Graph;
 273          Vertex : Library_Graph_Vertex_Id) return Boolean;
 274       pragma Inline (Is_Suitable_Weakly_Elaborable_Vertex);
 275       --  Determine whether vertex Vertex of library graph G is suitable for
 276       --  weak elaboration.
 277
 278       procedure Set_Unit_Elaboration_Positions (Order : Unit_Id_Table);
 279       pragma Inline (Set_Unit_Elaboration_Positions);
 280       --  Set the ALI.Units positions of all elaboration units in order Order
 281
 282       procedure Trace_Component
 283         (G    : Library_Graph;
 284          Comp : Component_Id;
 285          Msg  : String;
 286          Step : Elaboration_Order_Step);
 287       pragma Inline (Trace_Component);
 288       --  Write elaboration-related information for component Comp of library
 289       --  graph G to standard output, starting with message Msg. Step is the
 290       --  current step in the elaboration order.
 291
 292       procedure Trace_Step (Step : Elaboration_Order_Step);
 293       pragma Inline (Trace_Step);
 294       --  Write current step Step of the elaboration order to standard output
 295
 296       procedure Trace_Vertex
 297         (G      : Library_Graph;
 298          Vertex : Library_Graph_Vertex_Id;
 299          Msg    : String;
 300          Step   : Elaboration_Order_Step;
 301          Indent : Indentation_Level);
 302       pragma Inline (Trace_Vertex);
 303       --  Write elaboration-related information for vertex Vertex of library
 304       --  graph G to standard output, starting with message Msg. Step is the
 305       --  current step in the elaboration order. Indent denotes the desired
 306       --  indentation level for tracing.
 307
 308       procedure Trace_Vertices
 309         (G          : Library_Graph;
 310          Set        : LGV_Sets.Membership_Set;
 311          Set_Msg    : String;
 312          Vertex_Msg : String;
 313          Step       : Elaboration_Order_Step;
 314          Indent     : Indentation_Level);
 315       pragma Inline (Trace_Vertices);
 316       --  Write the candidate vertices of library graph G present in membership
 317       --  set Set to standard output, starting with message Set_Msg. Vertex_Msg
 318       --  is the message emitted prior to each vertex. Step denotes the current
 319       --  step in the elaboration order. Indent denotes the desired indentation
 320       --  level for tracing.
 321
 322       procedure Update_Successor
 323         (G                        : Library_Graph;
 324          Edge                     : Library_Graph_Edge_Id;
 325          All_Elaborable_Vertices  : LGV_Sets.Membership_Set;
 326          All_Waiting_Vertices     : LGV_Sets.Membership_Set;
 327          Comp_Elaborable_Vertices : LGV_Sets.Membership_Set;
 328          Comp_Waiting_Vertices    : LGV_Sets.Membership_Set;
 329          Step                     : Elaboration_Order_Step;
 330          Indent                   : Indentation_Level);
 331       pragma Inline (Update_Successor);
 332       --  Notify the successor of edge Edge of library graph G along with its
 333       --  component that their predecessor has just been elaborated. This may
 334       --  cause new vertices to become elaborable. The sets contain vertices
 335       --  arranged as follows:
 336       --
 337       --    * All_Elaborable_Vertices - all elaborable vertices in the library
 338       --      graph.
 339       --
 340       --    * All_Waiting_Vertices - all vertices in the library graph that are
 341       --      waiting on predecessors to be elaborated.
 342       --
 343       --    * Comp_Elaborable_Vertices - all elaborable vertices found in the
 344       --      component of Vertex.
 345       --
 346       --    * Comp_Waiting_Vertices - all vertices found in the component of
 347       --      Vertex that are still waiting on predecessors to be elaborated.
 348       --
 349       --  Step is the current step in the elaboration order. Indent denotes the
 350       --  desired indentation level for tracing.
 351
 352       procedure Update_Successors
 353         (G                        : Library_Graph;
 354          Vertex                   : Library_Graph_Vertex_Id;
 355          All_Elaborable_Vertices  : LGV_Sets.Membership_Set;
 356          All_Waiting_Vertices     : LGV_Sets.Membership_Set;
 357          Comp_Elaborable_Vertices : LGV_Sets.Membership_Set;
 358          Comp_Waiting_Vertices    : LGV_Sets.Membership_Set;
 359          Step                     : Elaboration_Order_Step;
 360          Indent                   : Indentation_Level);
 361       pragma Inline (Update_Successors);
 362       --  Notify all successors of vertex Vertex of library graph G along with
 363       --  their components that their predecessor has just been elaborated.
 364       --  This may cause new vertices to become elaborable. The sets contain
 365       --  vertices arranged as follows:
 366       --
 367       --    * All_Elaborable_Vertices - all elaborable vertices in the library
 368       --      graph.
 369       --
 370       --    * All_Waiting_Vertices - all vertices in the library graph that are
 371       --      waiting on predecessors to be elaborated.
 372       --
 373       --    * Comp_Elaborable_Vertices - all elaborable vertices found in the
 374       --      component of Vertex.
 375       --
 376       --    * Comp_Waiting_Vertices - all vertices found in the component of
 377       --      Vertex that are still waiting on predecessors to be elaborated.
 378       --
 379       --  Step is the current step in the elaboration order. Indent denotes the
 380       --  desired indentation level for tracing.
 381
 382       ----------------------------------
 383       -- Create_Component_Vertex_Sets --
 384       ----------------------------------
 385
 386       procedure Create_Component_Vertex_Sets
 387         (G                   : Library_Graph;
 388          Comp                : Component_Id;
 389          Elaborable_Vertices : out LGV_Sets.Membership_Set;
 390          Waiting_Vertices    : out LGV_Sets.Membership_Set;
 391          Step                : Elaboration_Order_Step)
 392       is
 393          pragma Assert (Present (G));
 394          pragma Assert (Present (Comp));
 395
 396          Num_Of_Vertices : constant Natural :=
 397                              Number_Of_Component_Vertices (G, Comp);
 398
 399          Iter   : Component_Vertex_Iterator;
 400          Vertex : Library_Graph_Vertex_Id;
 401
 402       begin
 403          Elaborable_Vertices := LGV_Sets.Create (Num_Of_Vertices);
 404          Waiting_Vertices    := LGV_Sets.Create (Num_Of_Vertices);
 405
 406          Iter := Iterate_Component_Vertices (G, Comp);
 407          while Has_Next (Iter) loop
 408             Next (Iter, Vertex);
 409
 410             --  Add the vertex to the proper set depending on whether it can be
 411             --  elaborated.
 412
 413             if Is_Elaborable_Vertex (G, Vertex) then
 414                Insert_Vertex
 415                  (G      => G,
 416                   Vertex => Vertex,
 417                   Set    => Elaborable_Vertices,
 418                   Msg    => "add elaborable component vertex",
 419                   Step   => Step,
 420                   Indent => No_Indentation);
 421
 422             else
 423                Insert_Vertex
 424                  (G      => G,
 425                   Vertex => Vertex,
 426                   Set    => Waiting_Vertices,
 427                   Msg    => "add waiting component vertex",
 428                   Step   => Step,
 429                   Indent => No_Indentation);
 430             end if;
 431          end loop;
 432       end Create_Component_Vertex_Sets;
 433
 434       ------------------------
 435       -- Create_Vertex_Sets --
 436       ------------------------
 437
 438       procedure Create_Vertex_Sets
 439         (G                   : Library_Graph;
 440          Elaborable_Vertices : out LGV_Sets.Membership_Set;
 441          Waiting_Vertices    : out LGV_Sets.Membership_Set;
 442          Step                : Elaboration_Order_Step)
 443       is
 444          pragma Assert (Present (G));
 445
 446          Num_Of_Vertices : constant Natural := Number_Of_Vertices (G);
 447
 448          Iter   : Library_Graphs.All_Vertex_Iterator;
 449          Vertex : Library_Graph_Vertex_Id;
 450
 451       begin
 452          Elaborable_Vertices := LGV_Sets.Create (Num_Of_Vertices);
 453          Waiting_Vertices    := LGV_Sets.Create (Num_Of_Vertices);
 454
 455          Iter := Iterate_All_Vertices (G);
 456          while Has_Next (Iter) loop
 457             Next (Iter, Vertex);
 458
 459             --  Add the vertex to the proper set depending on whether it can be
 460             --  elaborated.
 461
 462             if Is_Elaborable_Vertex (G, Vertex) then
 463                Insert_Vertex
 464                  (G      => G,
 465                   Vertex => Vertex,
 466                   Set    => Elaborable_Vertices,
 467                   Msg    => "add elaborable vertex",
 468                   Step   => Step,
 469                   Indent => No_Indentation);
 470
 471             else
 472                Insert_Vertex
 473                  (G      => G,
 474                   Vertex => Vertex,
 475                   Set    => Waiting_Vertices,
 476                   Msg    => "add waiting vertex",
 477                   Step   => Step,
 478                   Indent => No_Indentation);
 479             end if;
 480          end loop;
 481       end Create_Vertex_Sets;
 482
 483       -------------------------
 484       -- Elaborate_Component --
 485       -------------------------
 486
 487       procedure Elaborate_Component
 488         (G                       : Library_Graph;
 489          Comp                    : Component_Id;
 490          All_Elaborable_Vertices : LGV_Sets.Membership_Set;
 491          All_Waiting_Vertices    : LGV_Sets.Membership_Set;
 492          Order                   : in out Unit_Id_Table;
 493          Step                    : Elaboration_Order_Step)
 494       is
 495          Comp_Elaborable_Vertices : LGV_Sets.Membership_Set;
 496          Comp_Waiting_Vertices    : LGV_Sets.Membership_Set;
 497          Vertex                   : Library_Graph_Vertex_Id;
 498
 499       begin
 500          pragma Assert (Present (G));
 501          pragma Assert (Present (Comp));
 502          pragma Assert (LGV_Sets.Present (All_Elaborable_Vertices));
 503          pragma Assert (LGV_Sets.Present (All_Waiting_Vertices));
 504
 505          Trace_Component
 506            (G    => G,
 507             Comp => Comp,
 508             Msg  => "elaborating component",
 509             Step => Step);
 510
 511          --  Divide all vertices of the component into an elaborable and
 512          --  waiting vertex set.
 513
 514          Create_Component_Vertex_Sets
 515            (G                   => G,
 516             Comp                => Comp,
 517             Elaborable_Vertices => Comp_Elaborable_Vertices,
 518             Waiting_Vertices    => Comp_Waiting_Vertices,
 519             Step                => Step);
 520
 521          loop
 522             Trace_Vertices
 523               (G          => G,
 524                Set        => Comp_Elaborable_Vertices,
 525                Set_Msg    => "elaborable component vertices",
 526                Vertex_Msg => "elaborable component vertex",
 527                Step       => Step,
 528                Indent     => Nested_Indentation);
 529
 530             Trace_Vertices
 531               (G          => G,
 532                Set        => Comp_Waiting_Vertices,
 533                Set_Msg    => "waiting component vertices",
 534                Vertex_Msg => "waiting component vertex",
 535                Step       => Step,
 536                Indent     => Nested_Indentation);
 537
 538             Vertex :=
 539               Find_Best_Elaborable_Vertex
 540                 (G      => G,
 541                  Set    => Comp_Elaborable_Vertices,
 542                  Step   => Step,
 543                  Indent => Nested_Indentation);
 544
 545             --  The component lacks an elaborable vertex. This indicates that
 546             --  either all vertices of the component have been elaborated or
 547             --  the graph has a circularity. Locate the best weak vertex that
 548             --  was compiled with the dynamic model to elaborate from the set
 549             --  waiting vertices. This action assumes that certain invocations
 550             --  will not take place at elaboration time. An order produced in
 551             --  this fashion may fail an ABE check at run time.
 552
 553             if not Present (Vertex) then
 554                Vertex :=
 555                  Find_Best_Weakly_Elaborable_Vertex
 556                    (G      => G,
 557                     Set    => Comp_Waiting_Vertices,
 558                     Step   => Step,
 559                     Indent => Nested_Indentation);
 560             end if;
 561
 562             --  Stop the elaboration when either all vertices of the component
 563             --  have been elaborated, or the graph contains a circularity.
 564
 565             exit when not Present (Vertex);
 566
 567             --  Try to elaborate as many vertices within the component as
 568             --  possible. Each successful elaboration signals the appropriate
 569             --  successors and components that they have one less predecessor
 570             --  to wait on.
 571
 572             Elaborate_Vertex
 573               (G                        => G,
 574                Vertex                   => Vertex,
 575                All_Elaborable_Vertices  => All_Elaborable_Vertices,
 576                All_Waiting_Vertices     => All_Waiting_Vertices,
 577                Comp_Elaborable_Vertices => Comp_Elaborable_Vertices,
 578                Comp_Waiting_Vertices    => Comp_Waiting_Vertices,
 579                Order                    => Order,
 580                Step                     => Step,
 581                Indent                   => Nested_Indentation);
 582          end loop;
 583
 584          LGV_Sets.Destroy (Comp_Elaborable_Vertices);
 585          LGV_Sets.Destroy (Comp_Waiting_Vertices);
 586       end Elaborate_Component;
 587
 588       -----------------------------
 589       -- Elaborate_Library_Graph --
 590       -----------------------------
 591
 592       procedure Elaborate_Library_Graph
 593         (G      : Library_Graph;
 594          Order  : out Unit_Id_Table;
 595          Status : out Elaboration_Order_Status)
 596       is
 597          Elaborable_Vertices : LGV_Sets.Membership_Set;
 598          Step                : Elaboration_Order_Step;
 599          Vertex              : Library_Graph_Vertex_Id;
 600          Waiting_Vertices    : LGV_Sets.Membership_Set;
 601
 602       begin
 603          pragma Assert (Present (G));
 604
 605          Step := Initial_Step;
 606
 607          --  Divide all vertices of the library graph into an elaborable and
 608          --  waiting vertex set.
 609
 610          Create_Vertex_Sets
 611            (G                   => G,
 612             Elaborable_Vertices => Elaborable_Vertices,
 613             Waiting_Vertices    => Waiting_Vertices,
 614             Step                => Step);
 615
 616          loop
 617             Step := Step + 1;
 618
 619             Trace_Vertices
 620               (G          => G,
 621                Set        => Elaborable_Vertices,
 622                Set_Msg    => "elaborable vertices",
 623                Vertex_Msg => "elaborable vertex",
 624                Step       => Step,
 625                Indent     => No_Indentation);
 626
 627             Trace_Vertices
 628               (G          => G,
 629                Set        => Waiting_Vertices,
 630                Set_Msg    => "waiting vertices",
 631                Vertex_Msg => "waiting vertex",
 632                Step       => Step,
 633                Indent     => No_Indentation);
 634
 635             Vertex :=
 636               Find_Best_Elaborable_Vertex
 637                 (G      => G,
 638                  Set    => Elaborable_Vertices,
 639                  Step   => Step,
 640                  Indent => No_Indentation);
 641
 642             --  The graph lacks an elaborable vertex. This indicates that
 643             --  either all vertices have been elaborated or the graph has a
 644             --  circularity. Find the best weak vertex that was compiled with
 645             --  the dynamic model to elaborate from set of waiting vertices.
 646             --  This action assumes that certain invocations will not take
 647             --  place at elaboration time. An order produced in this fashion
 648             --  may fail an ABE check at run time.
 649
 650             if not Present (Vertex) then
 651                Vertex :=
 652                  Find_Best_Weakly_Elaborable_Vertex
 653                    (G      => G,
 654                     Set    => Waiting_Vertices,
 655                     Step   => Step,
 656                     Indent => No_Indentation);
 657             end if;
 658
 659             --  Stop the elaboration when either all vertices of the graph have
 660             --  been elaborated, or the graph contains a circularity.
 661
 662             exit when not Present (Vertex);
 663
 664             --  Elaborate the component of the vertex by trying to elaborate as
 665             --  many vertices within the component as possible. Each successful
 666             --  elaboration signals the appropriate successors and components
 667             --  that they have one less predecessor to wait on.
 668
 669             Elaborate_Component
 670               (G                       => G,
 671                Comp                    => Component (G, Vertex),
 672                All_Elaborable_Vertices => Elaborable_Vertices,
 673                All_Waiting_Vertices    => Waiting_Vertices,
 674                Order                   => Order,
 675                Step                    => Step);
 676          end loop;
 677
 678          --  The graph contains an Elaborate_All circularity when at least one
 679          --  edge subject to the related pragma appears in a component.
 680
 681          if Has_Elaborate_All_Cycle (G) then
 682             Status := Order_Has_Elaborate_All_Circularity;
 683
 684          --  The graph contains a circularity when at least one vertex failed
 685          --  to elaborate.
 686
 687          elsif LGV_Sets.Size (Waiting_Vertices) /= 0 then
 688             Status := Order_Has_Circularity;
 689
 690          --  Otherwise the elaboration order is satisfactory
 691
 692          else
 693             Status := Order_OK;
 694          end if;
 695
 696          LGV_Sets.Destroy (Elaborable_Vertices);
 697          LGV_Sets.Destroy (Waiting_Vertices);
 698       end Elaborate_Library_Graph;
 699
 700       ---------------------
 701       -- Elaborate_Units --
 702       ---------------------
 703
 704       procedure Elaborate_Units
 705         (Order         : out Unit_Id_Table;
 706          Main_Lib_File : File_Name_Type)
 707       is
 708          pragma Unreferenced (Main_Lib_File);
 709
 710          Inv_Graph : Invocation_Graph;
 711          Lib_Graph : Library_Graph;
 712          Status    : Elaboration_Order_Status;
 713
 714       begin
 715          Start_Phase (Unit_Elaboration);
 716
 717          --  Initialize all unit-related data structures and gather all units
 718          --  that need elaboration.
 719
 720          Initialize_Units;
 721          Collect_Elaborable_Units;
 722
 723          --  Create the library graph that captures the dependencies between
 724          --  library items.
 725
 726          Lib_Graph := Build_Library_Graph;
 727
 728          --  Create the invocation graph that represents the flow of execution
 729
 730          Inv_Graph := Build_Invocation_Graph (Lib_Graph);
 731
 732          --  Traverse the invocation graph starting from elaboration code in
 733          --  order to discover transitions of the execution flow from a unit
 734          --  to a unit that result in extra edges within the library graph.
 735
 736          Augment_Library_Graph (Inv_Graph);
 737
 738          --  Create the component graph by collapsing all library items into
 739          --  library units and traversing the library graph.
 740
 741          Find_Components (Lib_Graph);
 742
 743          --  Output the contents of the ALI tables and both graphs to standard
 744          --  output now that they have been fully decorated.
 745
 746          Write_ALI_Tables;
 747          Write_Invocation_Graph (Inv_Graph);
 748          Write_Library_Graph    (Lib_Graph);
 749
 750          --  Traverse the library graph to determine the elaboration order of
 751          --  units.
 752
 753          Elaborate_Library_Graph (Lib_Graph, Order, Status);
 754
 755          --  The elaboration order is satisfactory
 756
 757          if Status = Order_OK then
 758             Validate_Elaboration_Order (Order);
 759
 760             --  Set attribute Elab_Position of table ALI.Units for all units in
 761             --  the elaboration order.
 762
 763             Set_Unit_Elaboration_Positions (Order);
 764
 765             --  Output the dependencies among units when switch -e (output
 766             --  complete list of elaboration order dependencies) is active.
 767
 768             Write_Dependencies (Lib_Graph);
 769
 770             --  Output the elaboration order when switch -l (output chosen
 771             --  elaboration order) is in effect.
 772
 773             Write_Elaboration_Order (Order);
 774
 775             --  Output the sources referenced in the closure of the order when
 776             --  switch -R (list sources referenced in closure) is in effect.
 777
 778             Write_Unit_Closure (Order);
 779
 780          --  Otherwise the library graph contains at least one circularity
 781
 782          else
 783             Diagnose_Circularities (Inv_Graph);
 784          end if;
 785
 786          Destroy (Inv_Graph);
 787          Destroy (Lib_Graph);
 788
 789          --  Destroy all unit-related data structures
 790
 791          Finalize_Units;
 792          End_Phase (Unit_Elaboration);
 793
 794          --  Halt the bind when there is no satisfactory elaboration order
 795
 796          if Status /= Order_OK then
 797             raise Unrecoverable_Error;
 798          end if;
 799       end Elaborate_Units;
 800
 801       ----------------------
 802       -- Elaborate_Vertex --
 803       ----------------------
 804
 805       procedure Elaborate_Vertex
 806         (G                        : Library_Graph;
 807          Vertex                   : Library_Graph_Vertex_Id;
 808          All_Elaborable_Vertices  : LGV_Sets.Membership_Set;
 809          All_Waiting_Vertices     : LGV_Sets.Membership_Set;
 810          Comp_Elaborable_Vertices : LGV_Sets.Membership_Set;
 811          Comp_Waiting_Vertices    : LGV_Sets.Membership_Set;
 812          Order                    : in out Unit_Id_Table;
 813          Step                     : Elaboration_Order_Step;
 814          Indent                   : Indentation_Level)
 815       is
 816       begin
 817          pragma Assert (Present (G));
 818          pragma Assert (Present (Vertex));
 819          pragma Assert (Needs_Elaboration (G, Vertex));
 820          pragma Assert (LGV_Sets.Present (All_Elaborable_Vertices));
 821          pragma Assert (LGV_Sets.Present (All_Waiting_Vertices));
 822          pragma Assert (LGV_Sets.Present (Comp_Elaborable_Vertices));
 823          pragma Assert (LGV_Sets.Present (Comp_Waiting_Vertices));
 824
 825          Trace_Vertex
 826            (G      => G,
 827             Vertex => Vertex,
 828             Msg    => "elaborating vertex",
 829             Step   => Step,
 830             Indent => Indent);
 831
 832          --  Remove the vertex from both elaborable sets. This is needed when
 833          --  the vertex is both an overall best candidate among all vertices,
 834          --  and the best candidate within the component.
 835
 836          LGV_Sets.Delete (All_Elaborable_Vertices,  Vertex);
 837          LGV_Sets.Delete (Comp_Elaborable_Vertices, Vertex);
 838
 839          --  Remove the vertex from both waiting sets. This is needed when a
 840          --  weakly elaborable vertex is both an overall best candidate among
 841          --  all waiting vertices and the best waiting candidate within the
 842          --  component.
 843
 844          LGV_Sets.Delete (All_Waiting_Vertices,  Vertex);
 845          LGV_Sets.Delete (Comp_Waiting_Vertices, Vertex);
 846
 847          --  Mark the vertex as elaborated in order to prevent further attempts
 848          --  to re-elaborate it.
 849
 850          Set_In_Elaboration_Order (G, Vertex);
 851
 852          --  Add the unit represented by the vertex to the elaboration order
 853
 854          Unit_Id_Tables.Append (Order, Unit (G, Vertex));
 855
 856          --  Notify all successors and their components that they have one
 857          --  fewer predecessor to wait on. This may cause some successors to
 858          --  be included in one of the sets.
 859
 860          Update_Successors
 861            (G                        => G,
 862             Vertex                   => Vertex,
 863             All_Elaborable_Vertices  => All_Elaborable_Vertices,
 864             All_Waiting_Vertices     => All_Waiting_Vertices,
 865             Comp_Elaborable_Vertices => Comp_Elaborable_Vertices,
 866             Comp_Waiting_Vertices    => Comp_Waiting_Vertices,
 867             Step                     => Step,
 868             Indent                   => Indent + Nested_Indentation);
 869
 870          --  Elaborate an eligible completing body immediately after its spec.
 871          --  This action satisfies the semantics of pragma Elaborate_Body. In
 872          --  addition, it ensures that a body will not "drift" too far from its
 873          --  spec in case invocation edges are removed from the library graph.
 874
 875          if Has_Elaborable_Body (G, Vertex) then
 876             Elaborate_Vertex
 877               (G                        => G,
 878                Vertex                   => Proper_Body (G, Vertex),
 879                All_Elaborable_Vertices  => All_Elaborable_Vertices,
 880                All_Waiting_Vertices     => All_Waiting_Vertices,
 881                Comp_Elaborable_Vertices => Comp_Elaborable_Vertices,
 882                Comp_Waiting_Vertices    => Comp_Waiting_Vertices,
 883                Order                    => Order,
 884                Step                     => Step,
 885                Indent                   => Indent);
 886          end if;
 887       end Elaborate_Vertex;
 888
 889       ---------------------------------
 890       -- Find_Best_Elaborable_Vertex --
 891       ---------------------------------
 892
 893       function Find_Best_Elaborable_Vertex
 894         (G      : Library_Graph;
 895          Set    : LGV_Sets.Membership_Set;
 896          Step   : Elaboration_Order_Step;
 897          Indent : Indentation_Level) return Library_Graph_Vertex_Id
 898       is
 899       begin
 900          pragma Assert (Present (G));
 901          pragma Assert (LGV_Sets.Present (Set));
 902
 903          return
 904            Find_Best_Vertex
 905              (G                   => G,
 906               Set                 => Set,
 907               Is_Suitable_Vertex  =>
 908                 Is_Suitable_Elaborable_Vertex'Access,
 909               Compare_Vertices    =>
 910                 Is_Better_Elaborable_Vertex'Access,
 911               Initial_Best_Msg    => "initial best elaborable vertex",
 912               Subsequent_Best_Msg => "better elaborable vertex",
 913               Step                => Step,
 914               Indent              => Indent);
 915       end Find_Best_Elaborable_Vertex;
 916
 917       ----------------------
 918       -- Find_Best_Vertex --
 919       ----------------------
 920
 921       function Find_Best_Vertex
 922         (G                   : Library_Graph;
 923          Set                 : LGV_Sets.Membership_Set;
 924          Is_Suitable_Vertex  : LGV_Predicate_Ptr;
 925          Compare_Vertices    : LGV_Comparator_Ptr;
 926          Initial_Best_Msg    : String;
 927          Subsequent_Best_Msg : String;
 928          Step                : Elaboration_Order_Step;
 929          Indent              : Indentation_Level)
 930          return Library_Graph_Vertex_Id
 931       is
 932          Best_Vertex    : Library_Graph_Vertex_Id;
 933          Current_Vertex : Library_Graph_Vertex_Id;
 934          Iter           : LGV_Sets.Iterator;
 935
 936       begin
 937          pragma Assert (Present (G));
 938          pragma Assert (LGV_Sets.Present (Set));
 939          pragma Assert (Is_Suitable_Vertex /= null);
 940          pragma Assert (Compare_Vertices /= null);
 941
 942          --  Assume that there is no candidate
 943
 944          Best_Vertex := No_Library_Graph_Vertex;
 945
 946          --  Inspect all vertices in the set, looking for the best candidate
 947          --  according to the comparator.
 948
 949          Iter := LGV_Sets.Iterate (Set);
 950          while LGV_Sets.Has_Next (Iter) loop
 951             LGV_Sets.Next (Iter, Current_Vertex);
 952             pragma Assert (Needs_Elaboration (G, Current_Vertex));
 953
 954             if Is_Suitable_Vertex.all (G, Current_Vertex) then
 955
 956                --  A previous iteration already picked the best candidate.
 957                --  Update the best candidate when the current vertex is a
 958                --  better choice.
 959
 960                if Present (Best_Vertex) then
 961                   if Compare_Vertices.all
 962                        (G           => G,
 963                         Vertex      => Current_Vertex,
 964                         Compared_To => Best_Vertex) = Higher_Precedence
 965                   then
 966                      Best_Vertex := Current_Vertex;
 967
 968                      Trace_Vertex
 969                        (G      => G,
 970                         Vertex => Best_Vertex,
 971                         Msg    => Subsequent_Best_Msg,
 972                         Step   => Step,
 973                         Indent => Indent);
 974                   end if;
 975
 976                --  Otherwise this is the first candidate
 977
 978                else
 979                   Best_Vertex := Current_Vertex;
 980
 981                   Trace_Vertex
 982                     (G      => G,
 983                      Vertex => Best_Vertex,
 984                      Msg    => Initial_Best_Msg,
 985                      Step   => Step,
 986                      Indent => Indent);
 987                end if;
 988             end if;
 989          end loop;
 990
 991          return Best_Vertex;
 992       end Find_Best_Vertex;
 993
 994       ----------------------------------------
 995       -- Find_Best_Weakly_Elaborable_Vertex --
 996       ----------------------------------------
 997
 998       function Find_Best_Weakly_Elaborable_Vertex
 999         (G      : Library_Graph;
1000          Set    : LGV_Sets.Membership_Set;
1001          Step   : Elaboration_Order_Step;
1002          Indent : Indentation_Level) return Library_Graph_Vertex_Id
1003       is
1004       begin
1005          pragma Assert (Present (G));
1006          pragma Assert (LGV_Sets.Present (Set));
1007
1008          return
1009            Find_Best_Vertex
1010              (G                   => G,
1011               Set                 => Set,
1012               Is_Suitable_Vertex  =>
1013                 Is_Suitable_Weakly_Elaborable_Vertex'Access,
1014               Compare_Vertices    =>
1015                 Is_Better_Weakly_Elaborable_Vertex'Access,
1016               Initial_Best_Msg    => "initial best weakly elaborable vertex",
1017               Subsequent_Best_Msg => "better weakly elaborable vertex",
1018               Step                => Step,
1019               Indent              => Indent);
1020       end Find_Best_Weakly_Elaborable_Vertex;
1021
1022       -------------------------
1023       -- Has_Elaborable_Body --
1024       -------------------------
1025
1026       function Has_Elaborable_Body
1027         (G      : Library_Graph;
1028          Vertex : Library_Graph_Vertex_Id) return Boolean
1029       is
1030       begin
1031          pragma Assert (Present (G));
1032          pragma Assert (Present (Vertex));
1033
1034          --  The body of an already-elaborated spec subject to Elaborate_Body
1035          --  is always elaborable.
1036
1037          if Is_Spec_With_Elaborate_Body (G, Vertex) then
1038             return True;
1039
1040          elsif Is_Spec_With_Body (G, Vertex) then
1041             return Is_Elaborable_Vertex (G, Proper_Body (G, Vertex));
1042          end if;
1043
1044          return False;
1045       end Has_Elaborable_Body;
1046
1047       ---------------------------------
1048       -- Insert_Elaborable_Successor --
1049       ---------------------------------
1050
1051       procedure Insert_Elaborable_Successor
1052         (G                     : Library_Graph;
1053          Vertex                : Library_Graph_Vertex_Id;
1054          Elaborable_Vertices   : LGV_Sets.Membership_Set;
1055          All_Waiting_Vertices  : LGV_Sets.Membership_Set;
1056          Comp_Waiting_Vertices : LGV_Sets.Membership_Set;
1057          Msg                   : String;
1058          Step                  : Elaboration_Order_Step;
1059          Indent                : Indentation_Level)
1060       is
1061          pragma Assert (Present (G));
1062          pragma Assert (Present (Vertex));
1063          pragma Assert (LGV_Sets.Present (Elaborable_Vertices));
1064          pragma Assert (LGV_Sets.Present (All_Waiting_Vertices));
1065          pragma Assert (LGV_Sets.Present (Comp_Waiting_Vertices));
1066
1067          Complement : constant Library_Graph_Vertex_Id :=
1068                         Complementary_Vertex
1069                           (G                => G,
1070                            Vertex           => Vertex,
1071                            Force_Complement => False);
1072
1073       begin
1074          --  Remove the successor from both waiting vertex sets because it may
1075          --  be the best vertex to elaborate across the whole graph and within
1076          --  its component.
1077
1078          LGV_Sets.Delete (All_Waiting_Vertices,  Vertex);
1079          LGV_Sets.Delete (Comp_Waiting_Vertices, Vertex);
1080
1081          Insert_Vertex
1082            (G      => G,
1083             Vertex => Vertex,
1084             Set    => Elaborable_Vertices,
1085             Msg    => Msg,
1086             Step   => Step,
1087             Indent => Indent);
1088
1089          if Present (Complement) then
1090
1091             --  Remove the complement of the successor from both waiting vertex
1092             --  sets because it may be the best vertex to elaborate across the
1093             --  whole graph and within its component.
1094
1095             LGV_Sets.Delete (All_Waiting_Vertices,  Complement);
1096             LGV_Sets.Delete (Comp_Waiting_Vertices, Complement);
1097
1098             Insert_Vertex
1099               (G      => G,
1100                Vertex => Complement,
1101                Set    => Elaborable_Vertices,
1102                Msg    => Msg,
1103                Step   => Step,
1104                Indent => Indent);
1105          end if;
1106       end Insert_Elaborable_Successor;
1107
1108       -------------------
1109       -- Insert_Vertex --
1110       -------------------
1111
1112       procedure Insert_Vertex
1113         (G      : Library_Graph;
1114          Vertex : Library_Graph_Vertex_Id;
1115          Set    : LGV_Sets.Membership_Set;
1116          Msg    : String;
1117          Step   : Elaboration_Order_Step;
1118          Indent : Indentation_Level)
1119       is
1120       begin
1121          pragma Assert (Present (G));
1122          pragma Assert (Present (Vertex));
1123          pragma Assert (Needs_Elaboration (G, Vertex));
1124          pragma Assert (LGV_Sets.Present (Set));
1125
1126          --  Nothing to do when the vertex is already present in the set
1127
1128          if LGV_Sets.Contains (Set, Vertex) then
1129             return;
1130          end if;
1131
1132          Trace_Vertex
1133            (G      => G,
1134             Vertex => Vertex,
1135             Msg    => Msg,
1136             Step   => Step,
1137             Indent => Indent);
1138
1139          --  Add the vertex to the set
1140
1141          LGV_Sets.Insert (Set, Vertex);
1142       end Insert_Vertex;
1143
1144       ---------------------------------
1145       -- Is_Better_Elaborable_Vertex --
1146       ---------------------------------
1147
1148       function Is_Better_Elaborable_Vertex
1149         (G           : Library_Graph;
1150          Vertex      : Library_Graph_Vertex_Id;
1151          Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind
1152       is
1153       begin
1154          pragma Assert (Present (G));
1155          pragma Assert (Present (Vertex));
1156          pragma Assert (Present (Compared_To));
1157
1158          --  Prefer a spec with Elaborate_Body over its corresponding body
1159
1160          if Is_Elaborate_Body_Pair
1161               (G           => G,
1162                Spec_Vertex => Vertex,
1163                Body_Vertex => Compared_To)
1164          then
1165             return Higher_Precedence;
1166
1167          elsif Is_Elaborate_Body_Pair
1168                  (G           => G,
1169                   Spec_Vertex => Compared_To,
1170                   Body_Vertex => Vertex)
1171          then
1172             return Lower_Precedence;
1173
1174          --  Prefer a predefined unit over a non-predefined unit
1175
1176          elsif Is_Predefined_Unit (G, Vertex)
1177            and then not Is_Predefined_Unit (G, Compared_To)
1178          then
1179             return Higher_Precedence;
1180
1181          elsif not Is_Predefined_Unit (G, Vertex)
1182            and then Is_Predefined_Unit (G, Compared_To)
1183          then
1184             return Lower_Precedence;
1185
1186          --  Prefer an internal unit over a non-internal unit
1187
1188          elsif Is_Internal_Unit (G, Vertex)
1189            and then not Is_Internal_Unit (G, Compared_To)
1190          then
1191             return Higher_Precedence;
1192
1193          elsif not Is_Internal_Unit (G, Vertex)
1194            and then Is_Internal_Unit (G, Compared_To)
1195          then
1196             return Lower_Precedence;
1197
1198          --  Prefer a preelaborated unit over a non-preelaborated unit
1199
1200          elsif Is_Preelaborated_Unit (G, Vertex)
1201            and then not Is_Preelaborated_Unit (G, Compared_To)
1202          then
1203             return Higher_Precedence;
1204
1205          elsif not Is_Preelaborated_Unit (G, Vertex)
1206            and then Is_Preelaborated_Unit (G, Compared_To)
1207          then
1208             return Lower_Precedence;
1209
1210          --  Otherwise default to lexicographical order to ensure deterministic
1211          --  behavior.
1212
1213          elsif Uname_Less (Name (G, Vertex), Name (G, Compared_To)) then
1214             return Higher_Precedence;
1215
1216          else
1217             return Lower_Precedence;
1218          end if;
1219       end Is_Better_Elaborable_Vertex;
1220
1221       ----------------------------------------
1222       -- Is_Better_Weakly_Elaborable_Vertex --
1223       ----------------------------------------
1224
1225       function Is_Better_Weakly_Elaborable_Vertex
1226         (G           : Library_Graph;
1227          Vertex      : Library_Graph_Vertex_Id;
1228          Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind
1229       is
1230          Comp_Strong_Preds   : Natural;
1231          Comp_Weak_Preds     : Natural;
1232          Vertex_Strong_Preds : Natural;
1233          Vertex_Weak_Preds   : Natural;
1234
1235       begin
1236          pragma Assert (Present (G));
1237          pragma Assert (Present (Vertex));
1238          pragma Assert (Present (Compared_To));
1239
1240          --  Obtain the number of pending predecessors for both candidates,
1241          --  taking into account Elaborate_Body pairs.
1242
1243          Pending_Predecessors_For_Elaboration
1244            (G            => G,
1245             Vertex       => Vertex,
1246             Strong_Preds => Vertex_Strong_Preds,
1247             Weak_Preds   => Vertex_Weak_Preds);
1248
1249          Pending_Predecessors_For_Elaboration
1250            (G            => G,
1251             Vertex       => Compared_To,
1252             Strong_Preds => Comp_Strong_Preds,
1253             Weak_Preds   => Comp_Weak_Preds);
1254
1255          --  Neither candidate should be waiting on strong predecessors,
1256          --  otherwise the candidate cannot be weakly elaborated.
1257
1258          pragma Assert (Vertex_Strong_Preds = 0);
1259          pragma Assert (Comp_Strong_Preds   = 0);
1260
1261          --  Prefer a unit with fewer weak predecessors over a unit with more
1262          --  weak predecessors.
1263
1264          if Vertex_Weak_Preds < Comp_Weak_Preds then
1265             return Higher_Precedence;
1266
1267          elsif Vertex_Weak_Preds > Comp_Weak_Preds then
1268             return Lower_Precedence;
1269
1270          --  Otherwise default to lexicographical order to ensure deterministic
1271          --  behavior.
1272
1273          elsif Uname_Less (Name (G, Vertex), Name (G, Compared_To)) then
1274             return Higher_Precedence;
1275
1276          else
1277             return Lower_Precedence;
1278          end if;
1279       end Is_Better_Weakly_Elaborable_Vertex;
1280
1281       -----------------------------------
1282       -- Is_Suitable_Elaborable_Vertex --
1283       -----------------------------------
1284
1285       function Is_Suitable_Elaborable_Vertex
1286         (G      : Library_Graph;
1287          Vertex : Library_Graph_Vertex_Id) return Boolean
1288       is
1289       begin
1290          pragma Assert (Present (G));
1291          pragma Assert (Present (Vertex));
1292
1293          --  A vertex is suitable for elaboration as long it is not waiting on
1294          --  any predecessors, ignoring the static or dynamic model.
1295
1296          return Is_Elaborable_Vertex (G, Vertex);
1297       end Is_Suitable_Elaborable_Vertex;
1298
1299       ------------------------------------------
1300       -- Is_Suitable_Weakly_Elaborable_Vertex --
1301       ------------------------------------------
1302
1303       function Is_Suitable_Weakly_Elaborable_Vertex
1304         (G      : Library_Graph;
1305          Vertex : Library_Graph_Vertex_Id) return Boolean
1306       is
1307       begin
1308          pragma Assert (Present (G));
1309          pragma Assert (Present (Vertex));
1310
1311          --  A vertex is suitable for weak elaboration when it is waiting on
1312          --  weak predecessors only, and the unit it represents was compiled
1313          --  using the dynamic model.
1314
1315          return
1316            Is_Dynamically_Elaborated (G, Vertex)
1317              and then Is_Weakly_Elaborable_Vertex (G, Vertex);
1318       end Is_Suitable_Weakly_Elaborable_Vertex;
1319
1320       ------------------------------------
1321       -- Set_Unit_Elaboration_Positions --
1322       ------------------------------------
1323
1324       procedure Set_Unit_Elaboration_Positions (Order : Unit_Id_Table) is
1325          U_Id : Unit_Id;
1326
1327       begin
1328          for Position in Unit_Id_Tables.First ..
1329                          Unit_Id_Tables.Last (Order)
1330          loop
1331             U_Id := Order.Table (Position);
1332
1333             ALI.Units.Table (U_Id).Elab_Position := Position;
1334          end loop;
1335       end Set_Unit_Elaboration_Positions;
1336
1337       ---------------------
1338       -- Trace_Component --
1339       ---------------------
1340
1341       procedure Trace_Component
1342         (G    : Library_Graph;
1343          Comp : Component_Id;
1344          Msg  : String;
1345          Step : Elaboration_Order_Step)
1346       is
1347       begin
1348          pragma Assert (Present (G));
1349          pragma Assert (Present (Comp));
1350
1351          --  Nothing to do when switch -d_T (output elaboration order and cycle
1352          --  detection trace information) is not in effect.
1353
1354          if not Debug_Flag_Underscore_TT then
1355             return;
1356          end if;
1357
1358          Trace_Step (Step);
1359          Write_Str  (Msg);
1360          Write_Str  (" (Comp_Id_");
1361          Write_Int  (Int (Comp));
1362          Write_Str  (")");
1363          Write_Eol;
1364
1365          Trace_Step (Step);
1366          Indent_By  (Nested_Indentation);
1367          Write_Str  ("pending strong predecessors: ");
1368          Write_Num  (Int (Pending_Strong_Predecessors (G, Comp)));
1369          Write_Eol;
1370
1371          Trace_Step (Step);
1372          Indent_By  (Nested_Indentation);
1373          Write_Str  ("pending weak predecessors  : ");
1374          Write_Num  (Int (Pending_Weak_Predecessors (G, Comp)));
1375          Write_Eol;
1376       end Trace_Component;
1377
1378       ----------------
1379       -- Trace_Step --
1380       ----------------
1381
1382       procedure Trace_Step (Step : Elaboration_Order_Step) is
1383       begin
1384          --  Nothing to do when switch -d_T (output elaboration order and cycle
1385          --  detection trace information) is not in effect.
1386
1387          if not Debug_Flag_Underscore_TT then
1388             return;
1389          end if;
1390
1391          Write_Num
1392            (Val        => Int (Step),
1393             Val_Indent => Step_Column);
1394          Write_Str (": ");
1395       end Trace_Step;
1396
1397       ------------------
1398       -- Trace_Vertex --
1399       ------------------
1400
1401       procedure Trace_Vertex
1402         (G      : Library_Graph;
1403          Vertex : Library_Graph_Vertex_Id;
1404          Msg    : String;
1405          Step   : Elaboration_Order_Step;
1406          Indent : Indentation_Level)
1407       is
1408          pragma Assert (Present (G));
1409          pragma Assert (Present (Vertex));
1410
1411          Attr_Indent : constant Indentation_Level :=
1412                          Indent + Nested_Indentation;
1413          Comp        : constant Component_Id := Component (G, Vertex);
1414
1415       begin
1416          --  Nothing to do when switch -d_T (output elaboration order and cycle
1417          --  detection trace information) is not in effect.
1418
1419          if not Debug_Flag_Underscore_TT then
1420             return;
1421          end if;
1422
1423          Trace_Step (Step);
1424          Indent_By  (Indent);
1425          Write_Str  (Msg);
1426          Write_Str  (" (LGV_Id_");
1427          Write_Int  (Int (Vertex));
1428          Write_Str  (")");
1429          Write_Eol;
1430
1431          Trace_Step (Step);
1432          Indent_By  (Attr_Indent);
1433          Write_Str  ("name = ");
1434          Write_Name (Name (G, Vertex));
1435          Write_Eol;
1436
1437          Trace_Step (Step);
1438          Indent_By  (Attr_Indent);
1439          Write_Str  ("Component (Comp_Id_");
1440          Write_Int  (Int (Comp));
1441          Write_Str  (")");
1442          Write_Eol;
1443
1444          Trace_Step (Step);
1445          Indent_By  (Attr_Indent);
1446          Write_Str  ("pending strong predecessors: ");
1447          Write_Num  (Int (Pending_Strong_Predecessors (G, Vertex)));
1448          Write_Eol;
1449
1450          Trace_Step (Step);
1451          Indent_By  (Attr_Indent);
1452          Write_Str  ("pending weak predecessors  : ");
1453          Write_Num  (Int (Pending_Weak_Predecessors (G, Vertex)));
1454          Write_Eol;
1455
1456          Trace_Step (Step);
1457          Indent_By  (Attr_Indent);
1458          Write_Str  ("pending strong components  : ");
1459          Write_Num  (Int (Pending_Strong_Predecessors (G, Comp)));
1460          Write_Eol;
1461
1462          Trace_Step (Step);
1463          Indent_By  (Attr_Indent);
1464          Write_Str  ("pending weak components    : ");
1465          Write_Num  (Int (Pending_Weak_Predecessors (G, Comp)));
1466          Write_Eol;
1467       end Trace_Vertex;
1468
1469       --------------------
1470       -- Trace_Vertices --
1471       --------------------
1472
1473       procedure Trace_Vertices
1474         (G          : Library_Graph;
1475          Set        : LGV_Sets.Membership_Set;
1476          Set_Msg    : String;
1477          Vertex_Msg : String;
1478          Step       : Elaboration_Order_Step;
1479          Indent     : Indentation_Level)
1480       is
1481          Vertex_Indent : constant Indentation_Level :=
1482                            Indent + Nested_Indentation;
1483
1484          Iter   : LGV_Sets.Iterator;
1485          Vertex : Library_Graph_Vertex_Id;
1486
1487       begin
1488          pragma Assert (Present (G));
1489          pragma Assert (LGV_Sets.Present (Set));
1490
1491          --  Nothing to do when switch -d_T (output elaboration order and cycle
1492          --  detection trace information) is not in effect.
1493
1494          if not Debug_Flag_Underscore_TT then
1495             return;
1496          end if;
1497
1498          Trace_Step (Step);
1499          Indent_By  (Indent);
1500          Write_Str  (Set_Msg);
1501          Write_Str  (": ");
1502          Write_Int  (Int (LGV_Sets.Size (Set)));
1503          Write_Eol;
1504
1505          Iter := LGV_Sets.Iterate (Set);
1506          while LGV_Sets.Has_Next (Iter) loop
1507             LGV_Sets.Next (Iter, Vertex);
1508
1509             Trace_Vertex
1510               (G      => G,
1511                Vertex => Vertex,
1512                Msg    => Vertex_Msg,
1513                Step   => Step,
1514                Indent => Vertex_Indent);
1515          end loop;
1516       end Trace_Vertices;
1517
1518       ----------------------
1519       -- Update_Successor --
1520       ----------------------
1521
1522       procedure Update_Successor
1523         (G                        : Library_Graph;
1524          Edge                     : Library_Graph_Edge_Id;
1525          All_Elaborable_Vertices  : LGV_Sets.Membership_Set;
1526          All_Waiting_Vertices     : LGV_Sets.Membership_Set;
1527          Comp_Elaborable_Vertices : LGV_Sets.Membership_Set;
1528          Comp_Waiting_Vertices    : LGV_Sets.Membership_Set;
1529          Step                     : Elaboration_Order_Step;
1530          Indent                   : Indentation_Level)
1531       is
1532          pragma Assert (Present (G));
1533          pragma Assert (Present (Edge));
1534          pragma Assert (LGV_Sets.Present (All_Elaborable_Vertices));
1535          pragma Assert (LGV_Sets.Present (All_Waiting_Vertices));
1536          pragma Assert (LGV_Sets.Present (Comp_Elaborable_Vertices));
1537          pragma Assert (LGV_Sets.Present (Comp_Waiting_Vertices));
1538
1539          Pred : constant Library_Graph_Vertex_Id := Predecessor (G, Edge);
1540          Succ : constant Library_Graph_Vertex_Id := Successor   (G, Edge);
1541
1542          pragma Assert (Needs_Elaboration (G, Pred));
1543          pragma Assert (Needs_Elaboration (G, Succ));
1544
1545          In_Different_Components : constant Boolean :=
1546                                      not In_Same_Component
1547                                            (G     => G,
1548                                             Left  => Pred,
1549                                             Right => Succ);
1550
1551          Succ_Comp     : constant Component_Id      := Component (G, Succ);
1552          Vertex_Indent : constant Indentation_Level :=
1553                            Indent + Nested_Indentation;
1554
1555          Iter   : Component_Vertex_Iterator;
1556          Vertex : Library_Graph_Vertex_Id;
1557
1558       begin
1559          Trace_Vertex
1560            (G      => G,
1561             Vertex => Succ,
1562             Msg    => "updating successor",
1563             Step   => Step,
1564             Indent => Indent);
1565
1566          --  Notify the successor that it has one less predecessor to wait on.
1567          --  This effectively eliminates the edge that links the two.
1568
1569          Decrement_Pending_Predecessors
1570            (G      => G,
1571             Vertex => Succ,
1572             Edge   => Edge);
1573
1574          --  The predecessor and successor reside in different components.
1575          --  Notify the successor component it has one fewer components to
1576          --  wait on.
1577
1578          if In_Different_Components then
1579             Decrement_Pending_Predecessors
1580               (G    => G,
1581                Comp => Succ_Comp,
1582                Edge => Edge);
1583          end if;
1584
1585          --  At this point the successor may become elaborable when its final
1586          --  predecessor or final predecessor component has been elaborated.
1587
1588          if Is_Elaborable_Vertex (G, Succ) then
1589
1590             --  The predecessor and successor reside in different components.
1591             --  The successor must not be added to the candidates of Pred's
1592             --  component because this will mix units from the two components.
1593             --  Instead, the successor is added to the set of all elaborable
1594             --  vertices.
1595
1596             if In_Different_Components then
1597                Insert_Elaborable_Successor
1598                  (G                     => G,
1599                   Vertex                => Succ,
1600                   Elaborable_Vertices   => All_Elaborable_Vertices,
1601                   All_Waiting_Vertices  => All_Waiting_Vertices,
1602                   Comp_Waiting_Vertices => Comp_Waiting_Vertices,
1603                   Msg                   => "add elaborable successor",
1604                   Step                  => Step,
1605                   Indent                => Vertex_Indent);
1606
1607             --  Otherwise the predecessor and successor reside within the same
1608             --  component. Pred's component gains another elaborable vertex.
1609
1610             else
1611                Insert_Elaborable_Successor
1612                  (G                     => G,
1613                   Vertex                => Succ,
1614                   Elaborable_Vertices   => Comp_Elaborable_Vertices,
1615                   All_Waiting_Vertices  => All_Waiting_Vertices,
1616                   Comp_Waiting_Vertices => Comp_Waiting_Vertices,
1617                   Msg                   =>
1618                     "add elaborable component successor",
1619                   Step                  => Step,
1620                   Indent                => Vertex_Indent);
1621             end if;
1622          end if;
1623
1624          --  At this point the successor component may become elaborable when
1625          --  its final predecessor component is elaborated. This in turn may
1626          --  allow vertices of the successor component to be elaborated.
1627
1628          if In_Different_Components
1629            and then Is_Elaborable_Component (G, Succ_Comp)
1630          then
1631             Iter := Iterate_Component_Vertices (G, Succ_Comp);
1632             while Has_Next (Iter) loop
1633                Next (Iter, Vertex);
1634
1635                if Is_Elaborable_Vertex (G, Vertex) then
1636                   Insert_Elaborable_Successor
1637                     (G                     => G,
1638                      Vertex                => Vertex,
1639                      Elaborable_Vertices   => All_Elaborable_Vertices,
1640                      All_Waiting_Vertices  => All_Waiting_Vertices,
1641                      Comp_Waiting_Vertices => Comp_Waiting_Vertices,
1642                      Msg                   => "add elaborable vertex",
1643                      Step                  => Step,
1644                      Indent                => Vertex_Indent);
1645                end if;
1646             end loop;
1647          end if;
1648       end Update_Successor;
1649
1650       -----------------------
1651       -- Update_Successors --
1652       -----------------------
1653
1654       procedure Update_Successors
1655         (G                        : Library_Graph;
1656          Vertex                   : Library_Graph_Vertex_Id;
1657          All_Elaborable_Vertices  : LGV_Sets.Membership_Set;
1658          All_Waiting_Vertices     : LGV_Sets.Membership_Set;
1659          Comp_Elaborable_Vertices : LGV_Sets.Membership_Set;
1660          Comp_Waiting_Vertices    : LGV_Sets.Membership_Set;
1661          Step                     : Elaboration_Order_Step;
1662          Indent                   : Indentation_Level)
1663       is
1664          Edge : Library_Graph_Edge_Id;
1665          Iter : Edges_To_Successors_Iterator;
1666
1667       begin
1668          pragma Assert (Present (G));
1669          pragma Assert (Present (Vertex));
1670          pragma Assert (Needs_Elaboration (G, Vertex));
1671          pragma Assert (LGV_Sets.Present (All_Elaborable_Vertices));
1672          pragma Assert (LGV_Sets.Present (All_Waiting_Vertices));
1673          pragma Assert (LGV_Sets.Present (Comp_Elaborable_Vertices));
1674          pragma Assert (LGV_Sets.Present (Comp_Waiting_Vertices));
1675
1676          Iter := Iterate_Edges_To_Successors (G, Vertex);
1677          while Has_Next (Iter) loop
1678             Next (Iter, Edge);
1679             pragma Assert (Predecessor (G, Edge) = Vertex);
1680
1681             Update_Successor
1682               (G                        => G,
1683                Edge                     => Edge,
1684                All_Elaborable_Vertices  => All_Elaborable_Vertices,
1685                All_Waiting_Vertices     => All_Waiting_Vertices,
1686                Comp_Elaborable_Vertices => Comp_Elaborable_Vertices,
1687                Comp_Waiting_Vertices    => Comp_Waiting_Vertices,
1688                Step                     => Step,
1689                Indent                   => Indent);
1690          end loop;
1691       end Update_Successors;
1692    end Invocation_And_Library_Graph_Elaborators;
1693
1694 end Bindo.Elaborators;