path: root/gcc/ada/bindo.adb

------------------------------------------------------------------------------
--                                                                          --
--                         GNAT COMPILER COMPONENTS                         --
--                                                                          --
--                                B I N D O                                 --
--                                                                          --
--                                 B o d y                                  --
--                                                                          --
--             Copyright (C) 2019, Free Software Foundation, Inc.           --
--                                                                          --
-- GNAT is free software;  you can  redistribute it  and/or modify it under --
-- terms of the  GNU General Public License as published  by the Free Soft- --
-- ware  Foundation;  either version 3,  or (at your option) any later ver- --
-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License --
-- for  more details.  You should have  received  a copy of the GNU General --
-- Public License  distributed with GNAT; see file COPYING3.  If not, go to --
-- http://www.gnu.org/licenses for a complete copy of the license.          --
--                                                                          --
-- GNAT was originally developed  by the GNAT team at  New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc.      --
--                                                                          --
------------------------------------------------------------------------------

with Binde;
with Opt;   use Opt;

with Bindo.Elaborators;
use  Bindo.Elaborators;

package body Bindo is

   ---------------------------------
   -- Elaboration-order mechanism --
   ---------------------------------

   --  The elaboration-order (EO) mechanism implemented in this unit and its
   --  children has the following objectives:
   --
   --    * Find an ordering of all library items (historically referred to as
   --      "units") in the bind which require elaboration, taking into account:
   --
   --        - The dependencies between units expressed in the form of with
   --          clauses.
   --
   --        - Pragmas Elaborate, Elaborate_All, Elaborate_Body, Preelaborable,
   --          and Pure.
   --
   --        - The flow of execution at elaboration time.
   --
   --        - Additional dependencies between units supplied to the binder by
   --          means of a forced-elaboration-order file.
   --
   --      The high-level idea empoyed by the EO mechanism is to construct two
   --      graphs and use the information they represent to find an ordering of
   --      all units.
   --
   --      The invocation graph represents the flow of execution at elaboration
   --      time.
   --
   --      The library graph captures the dependencies between units expressed
   --      by with clause and elaboration-related pragmas. The library graph is
   --      further augmented with additional information from the invocation
   --      graph by exploring the execution paths from a unit with elaboration
   --      code to other external units.
   --
   --      The strongly connected components of the library graph are computed.
   --
   --      The order is obtained using a topological sort-like algorithm which
   --      traverses the library graph and its strongly connected components in
   --      an attempt to order available units while enabling other units to be
   --      ordered.
   --
   --    * Diagnose elaboration circularities between units
   --
   --      An elaboration circularity arises when either
   --
   --        - At least one unit cannot be ordered, or
   --
   --        - All units can be ordered, but an edge with an Elaborate_All
   --          pragma links two vertices within the same component of the
   --          library graph.
   --
   --      The library graph is traversed to discover, collect, and sort all
   --      cycles that hinder the elaboration order.
   --
   --      The most important cycle is diagnosed by describing its effects on
   --      the elaboration order and listing all units comprising the circuit.
   --      Various suggestions on how to break the cycle are offered.

   -----------------
   -- Terminology --
   -----------------

   --  * Component - A strongly connected component of a graph.
   --
   --  * Elaborable component - A component that is not waiting on other
   --    components to be elaborated.
   --
   --  * Elaborable vertex - A vertex that is not waiting on strong and weak
   --    predecessors, and whose component is elaborable.
   --
   --  * Elaboration circularity - A cycle involving units from the bind.
   --
   --  * Elaboration root - A special invocation construct which denotes the
   --    elaboration procedure of a unit.
   --
   --  * Invocation - The act of activating a task, calling a subprogram, or
   --    instantiating a generic.
   --
   --  * Invocation construct - An entry declaration, [single] protected type,
   --    subprogram declaration, subprogram instantiation, or a [single] task
   --    type declared in the visible, private, or body declarations of some
   --    unit. The construct is encoded in the ALI file of the related unit.
   --
   --  * Invocation graph - A directed graph which models the flow of execution
   --    at elaboration time.
   --
   --      - Vertices - Invocation constructs plus extra information. Certain
   --        vertices act as elaboration roots.
   --
   --      - Edges - Invocation relations plus extra information.
   --
   --  * Invocation relation - A flow link between two invocation constructs.
   --    This link is encoded in the ALI file of unit that houses the invoker.
   --
   --  * Invocation signature - A set of attributes that uniquely identify an
   --    invocation construct within the namespace of all ALI files.
   --
   --  * Invoker - The source construct of an invocation relation (the caller,
   --    instantiator, or task activator).
   --
   --  * Library graph - A directed graph which captures with clause and pragma
   --    dependencies between units.
   --
   --      - Vertices - Units plus extra information.
   --
   --      - Edges - With clause, pragma, and additional dependencies between
   --        units.
   --
   --  * Pending predecessor - A vertex that must be elaborated before another
   --    vertex can be elaborated.
   --
   --  * Strong edge - A non-invocation library graph edge. Strong edges
   --    represent the language-defined relations between units.
   --
   --  * Strong predecessor - A library graph vertex reachable via a strong
   --    edge.
   --
   --  * Target - The destination construct of an invocation relation (the
   --    generic, subprogram, or task type).
   --
   --  * Weak edge - An invocation library graph edge. Weak edges represent
   --    the speculative flow of execution at elaboration time, which may or
   --    may not take place.
   --
   --  * Weak predecessor - A library graph vertex reachable via a weak edge.
   --
   --  * Weakly elaborable vertex - A vertex that is waiting solely on weak
   --    predecessors to be elaborated, and whose component is elaborable.

   ------------------
   -- Architecture --
   ------------------

   --     Find_Elaboration_Order
   --     |
   --     +--> Collect_Elaborable_Units
   --     +--> Write_ALI_Tables
   --     +--> Elaborate_Units
   --          |
   --  +------ | -------------- Construction phase ------------------------+
   --  |       |                                                           |
   --  |       +--> Build_Library_Graph                                    |
   --  |       +--> Validate_Library_Graph                                 |
   --  |       +--> Write_Library_Graph                                    |
   --  |       |                                                           |
   --  |       +--> Build_Invocation_Graph                                 |
   --  |       +--> Validate_Invocation_Graph                              |
   --  |       +--> Write_Invocation_Graph                                 |
   --  |       |                                                           |
   --  +------ | ----------------------------------------------------------+
   --          |
   --  +------ | -------------- Augmentation phase ------------------------+
   --  |       |                                                           |
   --  |       +--> Augment_Library_Graph                                  |
   --  |       |                                                           |
   --  +------ | ----------------------------------------------------------+
   --          |
   --  +------ | -------------- Ordering phase ----------------------------+
   --  |       |                                                           |
   --  |       +--> Find_Components                                        |
   --  |       |                                                           |
   --  |       +--> Elaborate_Library_Graph                                |
   --  |       +--> Validate_Elaboration_Order                             |
   --  |       +--> Write_Elaboration_Order                                |
   --  |       |                                                           |
   --  |       +--> Write_Unit_Closure                                     |
   --  |       |                                                           |
   --  +------ | ----------------------------------------------------------+
   --          |
   --  +------ | -------------- Diagnostics phase -------------------------+
   --  |       |                                                           |
   --  |       +--> Find_Cycles                                            |
   --  |       +--> Validate_Cycles                                        |
   --  |       +--> Write_Cycles                                           |
   --  |       |                                                           |
   --  |       +--> Diagnose_Cycle / Diagnose_All_Cycles                   |
   --  |                                                                   |
   --  +-------------------------------------------------------------------+

   ------------------------
   -- Construction phase --
   ------------------------

   --  The Construction phase has the following objectives:
   --
   --    * Build the library graph by inspecting the ALI file of each unit that
   --      requires elaboration.
   --
   --    * Validate the consistency of the library graph, only when switch -d_V
   --      is in effect.
   --
   --    * Write the contents of the invocation graph in human-readable form to
   --      standard output when switch -d_L is in effect.
   --
   --    * Build the invocation graph by inspecting invocation constructs and
   --      relations in the ALI file of each unit that requires elaboration.
   --
   --    * Validate the consistency of the invocation graph, only when switch
   --      -d_V is in effect.
   --
   --    * Write the contents of the invocation graph in human-readable form to
   --      standard output when switch -d_I is in effect.

   ------------------------
   -- Augmentation phase --
   ------------------------

   --  The Augmentation phase has the following objectives:
   --
   --    * Discover transitions of the elaboration flow from a unit with an
   --      elaboration root to other units. Augment the library graph with
   --      extra edges for each such transition.

   --------------------
   -- Ordering phase --
   --------------------

   --  The Ordering phase has the following objectives:
   --
   --    * Discover all components of the library graph by treating specs and
   --      bodies as single vertices.
   --
   --    * Try to order as many vertices of the library graph as possible by
   --      performing a topological sort based on the pending predecessors of
   --      vertices across all components and within a single component.
   --
   --    * Validate the consistency of the order, only when switch -d_V is in
   --      effect.
   --
   --    * Write the contents of the order in human-readable form to standard
   --      output when switch -d_O is in effect.
   --
   --    * Write the sources of the order closure when switch -R is in effect.

   -----------------------
   -- Diagnostics phase --
   -----------------------

   --  The Diagnostics phase has the following objectives:
   --
   --    * Discover, save, and sort all cycles in the library graph. The cycles
   --      are sorted based on the following heuristics:
   --
   --        - A cycle with higher precedence is preferred.
   --
   --        - A cycle with fewer invocation edges is preferred.
   --
   --        - A cycle with a shorter length is preferred.
   --
   --    * Validate the consistency of cycles, only when switch -d_V is in
   --      effect.
   --
   --    * Write the contents of all cycles in human-readable form to standard
   --      output when switch -d_O is in effect.
   --
   --    * Diagnose the most important cycle, or all cycles when switch -d_C is
   --      in effect. The diagnostic consists of:
   --
   --        - The reason for the existence of the cycle, along with the unit
   --          whose elaboration cannot be guaranteed.
   --
   --        - A detailed traceback of the cycle, showcasing the transition
   --          between units, along with any other elaboration-order-related
   --          information.
   --
   --        - A set of suggestions on how to break the cycle considering the
   --          the edges comprising the circuit, the elaboration model used to
   --          compile the units, the availability of invocation information,
   --          and the state of various relevant switches.

   --------------
   -- Switches --
   --------------

   --  -d_a  Ignore the effects of pragma Elaborate_All
   --
   --        GNATbind creates a regular with edge instead of an Elaborate_All
   --        edge in the library graph, thus eliminating the effects of the
   --        pragma.
   --
   --  -d_b  Ignore the effects of pragma Elaborate_Body
   --
   --        GNATbind treats a spec and body pair as decoupled.
   --
   --  -d_e  Ignore the effects of pragma Elaborate
   --
   --        GNATbind creates a regular with edge instead of an Elaborate edge
   --        in the library graph, thus eliminating the effects of the pragma.
   --        In addition, GNATbind does not create an edge to the body of the
   --        pragma argument.
   --
   --  -d_t  Output cycle-detection trace information
   --
   --        GNATbind outputs trace information on cycle-detection activities
   --        to standard output.
   --
   --  -d_A  Output ALI invocation tables
   --
   --        GNATbind outputs the contents of ALI table Invocation_Constructs
   --        and Invocation_Edges in textual format to standard output.
   --
   --  -d_C  Diagnose all cycles
   --
   --        GNATbind outputs diagnostics for all unique cycles in the bind,
   --        rather than just the most important one.
   --
   --  -d_I  Output invocation graph
   --
   --        GNATbind outputs the invocation graph in text format to standard
   --        output.
   --
   --  -d_L  Output library graph
   --
   --        GNATbind outputs the library graph in textual format to standard
   --        output.
   --
   --  -d_N  New bindo order
   --
   --        GNATbind utilizes the new bindo elaboration order
   --
   --  -d_P  Output cycle paths
   --
   --        GNATbind output the cycle paths in text format to standard output
   --
   --  -d_T  Output elaboration-order trace information
   --
   --        GNATbind outputs trace information on elaboration-order detection
   --        activities to standard output.
   --
   --  -d_V  Validate bindo cycles, graphs, and order
   --
   --        GNATbind validates the invocation graph, library graph along with
   --        its cycles, and elaboration order by detecting inconsistencies and
   --        producing error reports.
   --
   --  -e    Output complete list of elaboration-order dependencies
   --
   --        GNATbind outputs the dependencies between units to standard
   --        output.
   --
   --  -f    Force elaboration order from given file
   --
   --        GNATbind applies an additional set of edges to the library graph.
   --        The edges are read from a file specified by the argument of the
   --        flag.
   --
   --  -H    Legacy elaboration-order model enabled
   --
   --        GNATbind uses the library-graph and heuristics-based elaboration-
   --        order model.
   --
   --  -l    Output chosen elaboration order
   --
   --        GNATbind outputs the elaboration order in text format to standard
   --        output.
   --
   --  -p    Pessimistic (worst-case) elaboration order
   --
   --        This switch is not used in Bindo and its children.

   ----------------------------------------
   -- Debugging elaboration-order issues --
   ----------------------------------------

   --  Prior to debugging elaboration-order-related issues, enable all relevant
   --  debug flags to collect as much information as possible. Depending on the
   --  number of files in the bind, Bindo may emit anywhere between several MBs
   --  to several hundred MBs of data to standard output. The switches are:
   --
   --    -d_A -d_C -d_I -d_L -d_P -d_t -d_T -d_V
   --
   --  Bindo offers several debugging routines that can be invoked from gdb.
   --  Those are defined in the body of Bindo.Writers, in sections denoted by
   --  header Debug. For quick reference, the routines are:
   --
   --    palgc  --  print all library-graph cycles
   --    pau    --  print all units
   --    pc     --  print component
   --    pige   --  print invocation-graph edge
   --    pigv   --  print invocation-graph vertex
   --    plgc   --  print library-graph cycle
   --    plge   --  print library-graph edge
   --    plgv   --  print library-graph vertex
   --    pu     --  print units
   --
   --  * Invalid elaboration order
   --
   --    The elaboration order is invalid when:
   --
   --      - A unit that requires elaboration is missing from the order
   --      - A unit that does not require elaboration is present in the order
   --
   --    Examine the output of the elaboration algorithm available via switch
   --    -d_T to determine how the related units were included in or excluded
   --    from the order. Determine whether the library graph contains all the
   --    relevant edges for those units.
   --
   --    Units and routines of interest:
   --      Bindo.Elaborators
   --      Elaborate_Library_Graph
   --      Elaborate_Units
   --
   --  * Invalid invocation graph
   --
   --    The invocation graph is invalid when:
   --
   --      - An edge lacks an attribute
   --      - A vertex lacks an attribute
   --
   --    Find the malformed edge or vertex and determine which attribute is
   --    missing. Examine the contents of the invocation-related ALI tables
   --    available via switch -d_A. If the invocation construct or relation
   --    is missing, verify the ALI file. If the ALI lacks all the relevant
   --    information, then Sem_Elab most likely failed to discover a valid
   --    elaboration path.
   --
   --    Units and routines of interest:
   --      Bindo.Builders
   --      Bindo.Graphs
   --      Add_Edge
   --      Add_Vertex
   --      Build_Invocation_Graph
   --
   --  * Invalid library graph
   --
   --    The library graph is invalid when:
   --
   --      - An edge lacks an attribute
   --      - A vertex lacks an attribute
   --
   --    Find the malformed edge or vertex and determine which attribute is
   --    missing.
   --
   --    Units and routines of interest:
   --      Bindo.Builders
   --      Bindo.Graphs
   --      Add_Edge
   --      Add_Vertex
   --      Build_Library_Graph
   --
   --  * Invalid library-graph cycle
   --
   --    A library-graph cycle is invalid when:
   --
   --      - It lacks enough edges to form a circuit
   --      - At least one edge in the circuit is repeated
   --
   --    Find the malformed cycle and determine which attribute is missing.
   --
   --    Units and routines of interest:
   --      Bindo.Graphs
   --      Find_Cycles

   ----------------------------
   -- Find_Elaboration_Order --
   ----------------------------

   procedure Find_Elaboration_Order
     (Order         : out Unit_Id_Table;
      Main_Lib_File : File_Name_Type)
   is
   begin
      --  Use the library graph and heuristic-based elaboration order when
      --  switch -H (legacy elaboration-order mode enabled).

      if Legacy_Elaboration_Order then
         Binde.Find_Elab_Order (Order, Main_Lib_File);

      --  Otherwise use the invocation and library-graph-based elaboration
      --  order.

      else
         Invocation_And_Library_Graph_Elaborators.Elaborate_Units
           (Order         => Order,
            Main_Lib_File => Main_Lib_File);
      end if;
   end Find_Elaboration_Order;

end Bindo;