1 ------------------------------------------------------------------------------
3 -- GNAT COMPILER COMPONENTS --
5 -- B I N D O . G R A P H S --
9 -- Copyright (C) 2019-2020, Free Software Foundation, Inc. --
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. --
21 -- GNAT was originally developed by the GNAT team at New York University. --
22 -- Extensive contributions were provided by Ada Core Technologies Inc. --
24 ------------------------------------------------------------------------------
26 -- For full architecture, see unit Bindo.
28 -- The following unit defines the various graphs used in determining the
29 -- elaboration order of units.
31 with Types; use Types;
33 with Bindo.Units; use Bindo.Units;
36 with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables;
37 with GNAT.Graphs; use GNAT.Graphs;
38 with GNAT.Lists; use GNAT.Lists;
39 with GNAT.Sets; use GNAT.Sets;
41 package Bindo.Graphs is
43 ---------------------------
44 -- Invocation graph edge --
45 ---------------------------
47 -- The following type denotes an invocation graph edge handle
49 type Invocation_Graph_Edge_Id is new Natural;
50 No_Invocation_Graph_Edge : constant Invocation_Graph_Edge_Id :=
51 Invocation_Graph_Edge_Id'First;
52 First_Invocation_Graph_Edge : constant Invocation_Graph_Edge_Id :=
53 No_Invocation_Graph_Edge + 1;
55 procedure Destroy_Invocation_Graph_Edge
56 (Edge : in out Invocation_Graph_Edge_Id);
57 pragma Inline (Destroy_Invocation_Graph_Edge);
58 -- Destroy invocation graph edge Edge
60 function Hash_Invocation_Graph_Edge
61 (Edge : Invocation_Graph_Edge_Id) return Bucket_Range_Type;
62 pragma Inline (Hash_Invocation_Graph_Edge);
63 -- Obtain the hash value of key Edge
65 function Present (Edge : Invocation_Graph_Edge_Id) return Boolean;
66 pragma Inline (Present);
67 -- Determine whether invocation graph edge Edge exists
69 package IGE_Lists is new Doubly_Linked_Lists
70 (Element_Type => Invocation_Graph_Edge_Id,
72 Destroy_Element => Destroy_Invocation_Graph_Edge);
74 ------------------------------
75 -- Invocation graph vertex --
76 ------------------------------
78 -- The following type denotes an invocation graph vertex handle
80 type Invocation_Graph_Vertex_Id is new Natural;
81 No_Invocation_Graph_Vertex : constant Invocation_Graph_Vertex_Id :=
82 Invocation_Graph_Vertex_Id'First;
83 First_Invocation_Graph_Vertex : constant Invocation_Graph_Vertex_Id :=
84 No_Invocation_Graph_Vertex + 1;
86 function Hash_Invocation_Graph_Vertex
87 (Vertex : Invocation_Graph_Vertex_Id) return Bucket_Range_Type;
88 pragma Inline (Hash_Invocation_Graph_Vertex);
89 -- Obtain the hash value of key Vertex
91 function Present (Vertex : Invocation_Graph_Vertex_Id) return Boolean;
92 pragma Inline (Present);
93 -- Determine whether invocation graph vertex Vertex exists
95 package IGV_Sets is new Membership_Sets
96 (Element_Type => Invocation_Graph_Vertex_Id,
98 Hash => Hash_Invocation_Graph_Vertex);
100 -------------------------
101 -- Library graph cycle --
102 -------------------------
104 type Library_Graph_Cycle_Id is new Natural;
105 No_Library_Graph_Cycle : constant Library_Graph_Cycle_Id :=
106 Library_Graph_Cycle_Id'First;
107 First_Library_Graph_Cycle : constant Library_Graph_Cycle_Id :=
108 No_Library_Graph_Cycle + 1;
110 procedure Destroy_Library_Graph_Cycle
111 (Cycle : in out Library_Graph_Cycle_Id);
112 pragma Inline (Destroy_Library_Graph_Cycle);
113 -- Destroy library graph cycle Cycle
115 function Hash_Library_Graph_Cycle
116 (Cycle : Library_Graph_Cycle_Id) return Bucket_Range_Type;
117 pragma Inline (Hash_Library_Graph_Cycle);
118 -- Obtain the hash value of key Cycle
120 function Present (Cycle : Library_Graph_Cycle_Id) return Boolean;
121 pragma Inline (Present);
122 -- Determine whether library graph cycle Cycle exists
124 package LGC_Lists is new Doubly_Linked_Lists
125 (Element_Type => Library_Graph_Cycle_Id,
127 Destroy_Element => Destroy_Library_Graph_Cycle);
129 ------------------------
130 -- Library graph edge --
131 ------------------------
133 -- The following type denotes a library graph edge handle
135 type Library_Graph_Edge_Id is new Natural;
136 No_Library_Graph_Edge : constant Library_Graph_Edge_Id :=
137 Library_Graph_Edge_Id'First;
138 First_Library_Graph_Edge : constant Library_Graph_Edge_Id :=
139 No_Library_Graph_Edge + 1;
141 procedure Destroy_Library_Graph_Edge
142 (Edge : in out Library_Graph_Edge_Id);
143 pragma Inline (Destroy_Library_Graph_Edge);
144 -- Destroy library graph edge Edge
146 function Hash_Library_Graph_Edge
147 (Edge : Library_Graph_Edge_Id) return Bucket_Range_Type;
148 pragma Inline (Hash_Library_Graph_Edge);
149 -- Obtain the hash value of key Edge
151 function Present (Edge : Library_Graph_Edge_Id) return Boolean;
152 pragma Inline (Present);
153 -- Determine whether library graph edge Edge exists
155 package LGE_Lists is new Doubly_Linked_Lists
156 (Element_Type => Library_Graph_Edge_Id,
158 Destroy_Element => Destroy_Library_Graph_Edge);
160 package LGE_Sets is new Membership_Sets
161 (Element_Type => Library_Graph_Edge_Id,
163 Hash => Hash_Library_Graph_Edge);
165 --------------------------
166 -- Library graph vertex --
167 --------------------------
169 -- The following type denotes a library graph vertex handle
171 type Library_Graph_Vertex_Id is new Natural;
172 No_Library_Graph_Vertex : constant Library_Graph_Vertex_Id :=
173 Library_Graph_Vertex_Id'First;
174 First_Library_Graph_Vertex : constant Library_Graph_Vertex_Id :=
175 No_Library_Graph_Vertex + 1;
177 procedure Destroy_Library_Graph_Vertex
178 (Vertex : in out Library_Graph_Vertex_Id);
179 pragma Inline (Destroy_Library_Graph_Vertex);
180 -- Destroy library graph vertex Vertex
182 function Hash_Library_Graph_Vertex
183 (Vertex : Library_Graph_Vertex_Id) return Bucket_Range_Type;
184 pragma Inline (Hash_Library_Graph_Vertex);
185 -- Obtain the hash value of key Vertex
187 function Present (Vertex : Library_Graph_Vertex_Id) return Boolean;
188 pragma Inline (Present);
189 -- Determine whether library graph vertex Vertex exists
191 package LGV_Lists is new Doubly_Linked_Lists
192 (Element_Type => Library_Graph_Vertex_Id,
194 Destroy_Element => Destroy_Library_Graph_Vertex);
196 package LGV_Sets is new Membership_Sets
197 (Element_Type => Library_Graph_Vertex_Id,
199 Hash => Hash_Library_Graph_Vertex);
201 -----------------------
202 -- Invocation_Graphs --
203 -----------------------
205 package Invocation_Graphs is
211 -- The following type denotes an invocation graph handle. Each instance
212 -- must be created using routine Create.
214 type Invocation_Graph is private;
215 Nil : constant Invocation_Graph;
217 ----------------------
218 -- Graph operations --
219 ----------------------
222 (G : Invocation_Graph;
223 Source : Invocation_Graph_Vertex_Id;
224 Target : Invocation_Graph_Vertex_Id;
225 IR_Id : Invocation_Relation_Id);
226 pragma Inline (Add_Edge);
227 -- Create a new edge in invocation graph G with source vertex Source and
228 -- destination vertex Target. IR_Id is the invocation relation the edge
232 (G : Invocation_Graph;
233 IC_Id : Invocation_Construct_Id;
234 Body_Vertex : Library_Graph_Vertex_Id;
235 Spec_Vertex : Library_Graph_Vertex_Id);
236 pragma Inline (Add_Vertex);
237 -- Create a new vertex in invocation graph G. IC_Id is the invocation
238 -- construct the vertex describes. Body_Vertex denotes the library graph
239 -- vertex where the invocation construct's body is declared. Spec_Vertex
240 -- is the library graph vertex where the invocation construct's spec is
244 (Initial_Vertices : Positive;
245 Initial_Edges : Positive) return Invocation_Graph;
246 pragma Inline (Create);
247 -- Create a new empty graph with vertex capacity Initial_Vertices and
248 -- edge capacity Initial_Edges.
250 procedure Destroy (G : in out Invocation_Graph);
251 pragma Inline (Destroy);
252 -- Destroy the contents of invocation graph G, rendering it unusable
254 function Present (G : Invocation_Graph) return Boolean;
255 pragma Inline (Present);
256 -- Determine whether invocation graph G exists
258 -----------------------
259 -- Vertex attributes --
260 -----------------------
263 (G : Invocation_Graph;
264 Vertex : Invocation_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
265 pragma Inline (Body_Vertex);
266 -- Obtain the library graph vertex where the body of the invocation
267 -- construct represented by vertex Vertex of invocation graph G is
271 (G : Invocation_Graph;
272 Vertex : Invocation_Graph_Vertex_Id) return Nat;
273 pragma Inline (Column);
274 -- Obtain the column number where the invocation construct vertex Vertex
275 -- of invocation graph G describes.
278 (G : Invocation_Graph;
279 Vertex : Invocation_Graph_Vertex_Id) return Invocation_Construct_Id;
280 pragma Inline (Construct);
281 -- Obtain the invocation construct vertex Vertex of invocation graph G
284 function Corresponding_Vertex
285 (G : Invocation_Graph;
286 IS_Id : Invocation_Signature_Id) return Invocation_Graph_Vertex_Id;
287 pragma Inline (Corresponding_Vertex);
288 -- Obtain the vertex of invocation graph G that corresponds to signature
292 (G : Invocation_Graph;
293 Vertex : Invocation_Graph_Vertex_Id) return Nat;
294 pragma Inline (Line);
295 -- Obtain the line number where the invocation construct vertex Vertex
296 -- of invocation graph G describes.
299 (G : Invocation_Graph;
300 Vertex : Invocation_Graph_Vertex_Id) return Name_Id;
301 pragma Inline (Name);
302 -- Obtain the name of the construct vertex Vertex of invocation graph G
306 (G : Invocation_Graph;
307 Vertex : Invocation_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
308 pragma Inline (Spec_Vertex);
309 -- Obtain the library graph vertex where the spec of the invocation
310 -- construct represented by vertex Vertex of invocation graph G is
313 ---------------------
314 -- Edge attributes --
315 ---------------------
318 (G : Invocation_Graph;
319 Edge : Invocation_Graph_Edge_Id) return Name_Id;
320 pragma Inline (Extra);
321 -- Obtain the extra name used in error diagnostics of edge Edge of
322 -- invocation graph G.
325 (G : Invocation_Graph;
326 Edge : Invocation_Graph_Edge_Id) return Invocation_Kind;
327 pragma Inline (Kind);
328 -- Obtain the nature of edge Edge of invocation graph G
331 (G : Invocation_Graph;
332 Edge : Invocation_Graph_Edge_Id) return Invocation_Relation_Id;
333 pragma Inline (Relation);
334 -- Obtain the relation edge Edge of invocation graph G describes
337 (G : Invocation_Graph;
338 Edge : Invocation_Graph_Edge_Id) return Invocation_Graph_Vertex_Id;
339 pragma Inline (Target);
340 -- Obtain the target vertex edge Edge of invocation graph G designates
346 function Invocation_Graph_Edge_Count
347 (G : Invocation_Graph;
348 Kind : Invocation_Kind) return Natural;
349 pragma Inline (Invocation_Graph_Edge_Count);
350 -- Obtain the total number of edges of kind Kind in invocation graph G
352 function Number_Of_Edges (G : Invocation_Graph) return Natural;
353 pragma Inline (Number_Of_Edges);
354 -- Obtain the total number of edges in invocation graph G
356 function Number_Of_Edges_To_Targets
357 (G : Invocation_Graph;
358 Vertex : Invocation_Graph_Vertex_Id) return Natural;
359 pragma Inline (Number_Of_Edges_To_Targets);
360 -- Obtain the total number of edges to targets vertex Vertex of
361 -- invocation graph G has.
363 function Number_Of_Elaboration_Roots
364 (G : Invocation_Graph) return Natural;
365 pragma Inline (Number_Of_Elaboration_Roots);
366 -- Obtain the total number of elaboration roots in invocation graph G
368 function Number_Of_Vertices (G : Invocation_Graph) return Natural;
369 pragma Inline (Number_Of_Vertices);
370 -- Obtain the total number of vertices in invocation graph G
376 -- The following type represents an iterator over all edges of an
379 type All_Edge_Iterator is private;
381 function Has_Next (Iter : All_Edge_Iterator) return Boolean;
382 pragma Inline (Has_Next);
383 -- Determine whether iterator Iter has more edges to examine
385 function Iterate_All_Edges
386 (G : Invocation_Graph) return All_Edge_Iterator;
387 pragma Inline (Iterate_All_Edges);
388 -- Obtain an iterator over all edges of invocation graph G
391 (Iter : in out All_Edge_Iterator;
392 Edge : out Invocation_Graph_Edge_Id);
393 pragma Inline (Next);
394 -- Return the current edge referenced by iterator Iter and advance to
395 -- the next available edge.
397 -- The following type represents an iterator over all vertices of an
400 type All_Vertex_Iterator is private;
402 function Has_Next (Iter : All_Vertex_Iterator) return Boolean;
403 pragma Inline (Has_Next);
404 -- Determine whether iterator Iter has more vertices to examine
406 function Iterate_All_Vertices
407 (G : Invocation_Graph) return All_Vertex_Iterator;
408 pragma Inline (Iterate_All_Vertices);
409 -- Obtain an iterator over all vertices of invocation graph G
412 (Iter : in out All_Vertex_Iterator;
413 Vertex : out Invocation_Graph_Vertex_Id);
414 pragma Inline (Next);
415 -- Return the current vertex referenced by iterator Iter and advance
416 -- to the next available vertex.
418 -- The following type represents an iterator over all edges that reach
419 -- targets starting from a particular source vertex.
421 type Edges_To_Targets_Iterator is private;
423 function Has_Next (Iter : Edges_To_Targets_Iterator) return Boolean;
424 pragma Inline (Has_Next);
425 -- Determine whether iterator Iter has more edges to examine
427 function Iterate_Edges_To_Targets
428 (G : Invocation_Graph;
429 Vertex : Invocation_Graph_Vertex_Id) return Edges_To_Targets_Iterator;
430 pragma Inline (Iterate_Edges_To_Targets);
431 -- Obtain an iterator over all edges to targets with source vertex
432 -- Vertex of invocation graph G.
435 (Iter : in out Edges_To_Targets_Iterator;
436 Edge : out Invocation_Graph_Edge_Id);
437 pragma Inline (Next);
438 -- Return the current edge referenced by iterator Iter and advance to
439 -- the next available edge.
441 -- The following type represents an iterator over all vertices of an
442 -- invocation graph that denote the elaboration procedure or a spec or
443 -- a body, referred to as elaboration root.
445 type Elaboration_Root_Iterator is private;
447 function Has_Next (Iter : Elaboration_Root_Iterator) return Boolean;
448 pragma Inline (Has_Next);
449 -- Determine whether iterator Iter has more elaboration roots to examine
451 function Iterate_Elaboration_Roots
452 (G : Invocation_Graph) return Elaboration_Root_Iterator;
453 pragma Inline (Iterate_Elaboration_Roots);
454 -- Obtain an iterator over all elaboration roots of invocation graph G
457 (Iter : in out Elaboration_Root_Iterator;
458 Root : out Invocation_Graph_Vertex_Id);
459 pragma Inline (Next);
460 -- Return the current elaboration root referenced by iterator Iter and
461 -- advance to the next available elaboration root.
469 procedure Destroy_Invocation_Graph_Vertex
470 (Vertex : in out Invocation_Graph_Vertex_Id);
471 pragma Inline (Destroy_Invocation_Graph_Vertex);
472 -- Destroy invocation graph vertex Vertex
474 -- The following type represents the attributes of an invocation graph
477 type Invocation_Graph_Vertex_Attributes is record
478 Body_Vertex : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
479 -- Reference to the library graph vertex where the body of this
482 Construct : Invocation_Construct_Id := No_Invocation_Construct;
483 -- Reference to the invocation construct this vertex represents
485 Spec_Vertex : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
486 -- Reference to the library graph vertex where the spec of this
490 No_Invocation_Graph_Vertex_Attributes :
491 constant Invocation_Graph_Vertex_Attributes :=
492 (Body_Vertex => No_Library_Graph_Vertex,
493 Construct => No_Invocation_Construct,
494 Spec_Vertex => No_Library_Graph_Vertex);
496 procedure Destroy_Invocation_Graph_Vertex_Attributes
497 (Attrs : in out Invocation_Graph_Vertex_Attributes);
498 pragma Inline (Destroy_Invocation_Graph_Vertex_Attributes);
499 -- Destroy the contents of attributes Attrs
501 package IGV_Tables is new Dynamic_Hash_Tables
502 (Key_Type => Invocation_Graph_Vertex_Id,
503 Value_Type => Invocation_Graph_Vertex_Attributes,
504 No_Value => No_Invocation_Graph_Vertex_Attributes,
505 Expansion_Threshold => 1.5,
506 Expansion_Factor => 2,
507 Compression_Threshold => 0.3,
508 Compression_Factor => 2,
510 Destroy_Value => Destroy_Invocation_Graph_Vertex_Attributes,
511 Hash => Hash_Invocation_Graph_Vertex);
517 procedure Destroy_Invocation_Graph_Edge
518 (Edge : in out Invocation_Graph_Edge_Id);
519 pragma Inline (Destroy_Invocation_Graph_Edge);
520 -- Destroy invocation graph edge Edge
522 -- The following type represents the attributes of an invocation graph
525 type Invocation_Graph_Edge_Attributes is record
526 Relation : Invocation_Relation_Id := No_Invocation_Relation;
527 -- Reference to the invocation relation this edge represents
530 No_Invocation_Graph_Edge_Attributes :
531 constant Invocation_Graph_Edge_Attributes :=
532 (Relation => No_Invocation_Relation);
534 procedure Destroy_Invocation_Graph_Edge_Attributes
535 (Attrs : in out Invocation_Graph_Edge_Attributes);
536 pragma Inline (Destroy_Invocation_Graph_Edge_Attributes);
537 -- Destroy the contents of attributes Attrs
539 package IGE_Tables is new Dynamic_Hash_Tables
540 (Key_Type => Invocation_Graph_Edge_Id,
541 Value_Type => Invocation_Graph_Edge_Attributes,
542 No_Value => No_Invocation_Graph_Edge_Attributes,
543 Expansion_Threshold => 1.5,
544 Expansion_Factor => 2,
545 Compression_Threshold => 0.3,
546 Compression_Factor => 2,
548 Destroy_Value => Destroy_Invocation_Graph_Edge_Attributes,
549 Hash => Hash_Invocation_Graph_Edge);
555 -- The following type represents a relation between a source and target
558 type Source_Target_Relation is record
559 Source : Invocation_Graph_Vertex_Id := No_Invocation_Graph_Vertex;
562 Target : Invocation_Graph_Vertex_Id := No_Invocation_Graph_Vertex;
563 -- The destination vertex
566 No_Source_Target_Relation :
567 constant Source_Target_Relation :=
568 (Source => No_Invocation_Graph_Vertex,
569 Target => No_Invocation_Graph_Vertex);
571 function Hash_Source_Target_Relation
572 (Rel : Source_Target_Relation) return Bucket_Range_Type;
573 pragma Inline (Hash_Source_Target_Relation);
574 -- Obtain the hash value of key Rel
576 package Relation_Sets is new Membership_Sets
577 (Element_Type => Source_Target_Relation,
579 Hash => Hash_Source_Target_Relation);
585 type Invocation_Graph_Edge_Counts is array (Invocation_Kind) of Natural;
591 function Hash_Invocation_Signature
592 (IS_Id : Invocation_Signature_Id) return Bucket_Range_Type;
593 pragma Inline (Hash_Invocation_Signature);
594 -- Obtain the hash value of key IS_Id
596 package Signature_Tables is new Dynamic_Hash_Tables
597 (Key_Type => Invocation_Signature_Id,
598 Value_Type => Invocation_Graph_Vertex_Id,
599 No_Value => No_Invocation_Graph_Vertex,
600 Expansion_Threshold => 1.5,
601 Expansion_Factor => 2,
602 Compression_Threshold => 0.3,
603 Compression_Factor => 2,
605 Destroy_Value => Destroy_Invocation_Graph_Vertex,
606 Hash => Hash_Invocation_Signature);
608 -----------------------
609 -- Elaboration roots --
610 -----------------------
612 package IGV_Sets is new Membership_Sets
613 (Element_Type => Invocation_Graph_Vertex_Id,
615 Hash => Hash_Invocation_Graph_Vertex);
621 package DG is new Directed_Graphs
622 (Vertex_Id => Invocation_Graph_Vertex_Id,
623 No_Vertex => No_Invocation_Graph_Vertex,
624 Hash_Vertex => Hash_Invocation_Graph_Vertex,
626 Edge_id => Invocation_Graph_Edge_Id,
627 No_Edge => No_Invocation_Graph_Edge,
628 Hash_Edge => Hash_Invocation_Graph_Edge,
631 -- The following type represents the attributes of an invocation graph
633 type Invocation_Graph_Attributes is record
634 Counts : Invocation_Graph_Edge_Counts := (others => 0);
637 Edge_Attributes : IGE_Tables.Dynamic_Hash_Table := IGE_Tables.Nil;
638 -- The map of edge -> edge attributes for all edges in the graph
640 Graph : DG.Directed_Graph := DG.Nil;
641 -- The underlying graph describing the relations between edges and
644 Relations : Relation_Sets.Membership_Set := Relation_Sets.Nil;
645 -- The set of relations between source and targets, used to prevent
646 -- duplicate edges in the graph.
648 Roots : IGV_Sets.Membership_Set := IGV_Sets.Nil;
649 -- The set of elaboration root vertices
651 Signature_To_Vertex : Signature_Tables.Dynamic_Hash_Table :=
652 Signature_Tables.Nil;
653 -- The map of signature -> vertex
655 Vertex_Attributes : IGV_Tables.Dynamic_Hash_Table := IGV_Tables.Nil;
656 -- The map of vertex -> vertex attributes for all vertices in the
660 type Invocation_Graph is access Invocation_Graph_Attributes;
661 Nil : constant Invocation_Graph := null;
667 type All_Edge_Iterator is new DG.All_Edge_Iterator;
668 type All_Vertex_Iterator is new DG.All_Vertex_Iterator;
669 type Edges_To_Targets_Iterator is new DG.Outgoing_Edge_Iterator;
670 type Elaboration_Root_Iterator is new IGV_Sets.Iterator;
671 end Invocation_Graphs;
677 package Library_Graphs is
679 -- The following type represents the various kinds of library graph
680 -- cycles. The ordering of kinds is significant, where a literal with
681 -- lower ordinal has a higher precedence than one with higher ordinal.
683 type Library_Graph_Cycle_Kind is
684 (Elaborate_Body_Cycle,
685 -- A cycle that involves at least one spec-body pair, where the
686 -- spec is subject to pragma Elaborate_Body. This is the highest
690 -- A cycle that involves at least one Elaborate edge
693 -- A cycle that involves at least one Elaborate_All edge
696 -- A cycle that involves at least one edge which is a byproduct of
697 -- the forced-elaboration-order file.
700 -- A cycle that involves at least one invocation edge. This is the
701 -- lowest precedence cycle.
705 -- The following type represents the various kinds of library edges
707 type Library_Graph_Edge_Kind is
708 (Body_Before_Spec_Edge,
709 -- Successor denotes spec, Predecessor denotes a body. This is a
710 -- special edge kind used only during the discovery of components.
711 -- Note that a body can never be elaborated before its spec.
714 -- Successor withs Predecessor, and has pragma Elaborate for it
717 -- Successor withs Predecessor, and has pragma Elaborate_All for it
720 -- Successor is forced to with Predecessor by virtue of an existing
721 -- elaboration order provided in a file.
724 -- An invocation construct in unit Successor invokes a target in unit
727 Spec_Before_Body_Edge,
728 -- Successor denotes a body, Predecessor denotes a spec
731 -- Successor withs Predecessor
739 -- The following type denotes a library graph handle. Each instance must
740 -- be created using routine Create.
742 type Library_Graph is private;
743 Nil : constant Library_Graph;
745 type LGE_Predicate_Ptr is access function
747 Edge : Library_Graph_Edge_Id) return Boolean;
749 type LGV_Comparator_Ptr is access function
751 Vertex : Library_Graph_Vertex_Id;
752 Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind;
754 type LGV_Predicate_Ptr is access function
756 Vertex : Library_Graph_Vertex_Id) return Boolean;
758 ----------------------
759 -- Graph operations --
760 ----------------------
764 Pred : Library_Graph_Vertex_Id;
765 Succ : Library_Graph_Vertex_Id;
766 Kind : Library_Graph_Edge_Kind;
767 Activates_Task : Boolean);
768 pragma Inline (Add_Edge);
769 -- Create a new edge in library graph G with source vertex Pred and
770 -- destination vertex Succ. Kind denotes the nature of the edge. Flag
771 -- Activates_Task should be set when the edge involves task activation.
776 pragma Inline (Add_Vertex);
777 -- Create a new vertex in library graph G. U_Id is the unit the vertex
781 (Initial_Vertices : Positive;
782 Initial_Edges : Positive) return Library_Graph;
783 pragma Inline (Create);
784 -- Create a new empty graph with vertex capacity Initial_Vertices and
785 -- edge capacity Initial_Edges.
787 procedure Destroy (G : in out Library_Graph);
788 pragma Inline (Destroy);
789 -- Destroy the contents of library graph G, rendering it unusable
791 procedure Find_Components (G : Library_Graph);
792 pragma Inline (Find_Components);
793 -- Find all components in library graph G
795 procedure Find_Cycles (G : Library_Graph);
796 pragma Inline (Find_Cycles);
797 -- Find all cycles in library graph G
799 function Highest_Precedence_Cycle
800 (G : Library_Graph) return Library_Graph_Cycle_Id;
801 pragma Inline (Highest_Precedence_Cycle);
802 -- Obtain the cycle with highest precedence among all other cycles of
805 function Present (G : Library_Graph) return Boolean;
806 pragma Inline (Present);
807 -- Determine whether library graph G exists
809 -----------------------
810 -- Vertex attributes --
811 -----------------------
815 Vertex : Library_Graph_Vertex_Id) return Component_Id;
816 pragma Inline (Component);
817 -- Obtain the component where vertex Vertex of library graph G resides
819 function Corresponding_Item
821 Vertex : Library_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
822 pragma Inline (Corresponding_Item);
823 -- Obtain the complementary vertex which represents the corresponding
824 -- spec or body of vertex Vertex of library graph G.
826 function Corresponding_Vertex
828 U_Id : Unit_Id) return Library_Graph_Vertex_Id;
829 pragma Inline (Corresponding_Vertex);
830 -- Obtain the corresponding vertex of library graph G which represents
833 procedure Decrement_Pending_Predecessors
835 Vertex : Library_Graph_Vertex_Id;
836 Edge : Library_Graph_Edge_Id);
837 pragma Inline (Decrement_Pending_Predecessors);
838 -- Decrease the number of pending predecessors vertex Vertex which was
839 -- reached via edge Edge of library graph G must wait until it can be
844 Vertex : Library_Graph_Vertex_Id) return File_Name_Type;
845 pragma Inline (File_Name);
846 -- Obtain the name of the file where vertex Vertex of library graph G
849 function In_Elaboration_Order
851 Vertex : Library_Graph_Vertex_Id) return Boolean;
852 pragma Inline (In_Elaboration_Order);
853 -- Determine whether vertex Vertex of library graph G is already in some
854 -- elaboration order.
856 function Invocation_Graph_Encoding
858 Vertex : Library_Graph_Vertex_Id)
859 return Invocation_Graph_Encoding_Kind;
860 pragma Inline (Invocation_Graph_Encoding);
861 -- Obtain the encoding format used to capture information related to
862 -- invocation vertices and edges that reside within vertex Vertex of
867 Vertex : Library_Graph_Vertex_Id) return Unit_Name_Type;
868 pragma Inline (Name);
869 -- Obtain the name of the unit which vertex Vertex of library graph G
872 procedure Pending_Predecessors_For_Elaboration
874 Vertex : Library_Graph_Vertex_Id;
875 Strong_Preds : out Natural;
876 Weak_Preds : out Natural);
877 pragma Inline (Pending_Predecessors_For_Elaboration);
878 -- Obtain the number of pending strong and weak predecessors of vertex
879 -- Vertex of library graph G, taking into account Elaborate_Body pairs.
880 -- Strong predecessors are returned in Strong_Preds. Weak predecessors
881 -- are returned in Weak_Preds.
883 function Pending_Strong_Predecessors
885 Vertex : Library_Graph_Vertex_Id) return Natural;
886 pragma Inline (Pending_Strong_Predecessors);
887 -- Obtain the number of pending strong predecessors vertex Vertex of
888 -- library graph G must wait on until it can be elaborated.
890 function Pending_Weak_Predecessors
892 Vertex : Library_Graph_Vertex_Id) return Natural;
893 pragma Inline (Pending_Weak_Predecessors);
894 -- Obtain the number of pending weak predecessors vertex Vertex of
895 -- library graph G must wait on until it can be elaborated.
897 procedure Set_Corresponding_Item
899 Vertex : Library_Graph_Vertex_Id;
900 Val : Library_Graph_Vertex_Id);
901 pragma Inline (Set_Corresponding_Item);
902 -- Set the complementary vertex which represents the corresponding
903 -- spec or body of vertex Vertex of library graph G to value Val.
905 procedure Set_In_Elaboration_Order
907 Vertex : Library_Graph_Vertex_Id;
908 Val : Boolean := True);
909 pragma Inline (Set_In_Elaboration_Order);
910 -- Mark vertex Vertex of library graph G as included in some elaboration
911 -- order depending on value Val.
915 Vertex : Library_Graph_Vertex_Id) return Unit_Id;
916 pragma Inline (Unit);
917 -- Obtain the unit vertex Vertex of library graph G represents
919 ---------------------
920 -- Edge attributes --
921 ---------------------
923 function Activates_Task
925 Edge : Library_Graph_Edge_Id) return Boolean;
926 pragma Inline (Activates_Task);
927 -- Determine whether edge Edge of library graph G activates a task
931 Edge : Library_Graph_Edge_Id) return Library_Graph_Edge_Kind;
932 pragma Inline (Kind);
933 -- Obtain the nature of edge Edge of library graph G
937 Edge : Library_Graph_Edge_Id) return Library_Graph_Vertex_Id;
938 pragma Inline (Predecessor);
939 -- Obtain the predecessor vertex of edge Edge of library graph G
943 Edge : Library_Graph_Edge_Id) return Library_Graph_Vertex_Id;
944 pragma Inline (Successor);
945 -- Obtain the successor vertex of edge Edge of library graph G
947 --------------------------
948 -- Component attributes --
949 --------------------------
951 procedure Decrement_Pending_Predecessors
954 Edge : Library_Graph_Edge_Id);
955 pragma Inline (Decrement_Pending_Predecessors);
956 -- Decrease the number of pending predecessors component Comp which was
957 -- reached via edge Edge of library graph G must wait on until it can be
960 function Pending_Strong_Predecessors
962 Comp : Component_Id) return Natural;
963 pragma Inline (Pending_Strong_Predecessors);
964 -- Obtain the number of pending strong predecessors component Comp of
965 -- library graph G must wait on until it can be elaborated.
967 function Pending_Weak_Predecessors
969 Comp : Component_Id) return Natural;
970 pragma Inline (Pending_Weak_Predecessors);
971 -- Obtain the number of pending weak predecessors component Comp of
972 -- library graph G must wait on until it can be elaborated.
974 ----------------------
975 -- Cycle attributes --
976 ----------------------
978 function Invocation_Edge_Count
980 Cycle : Library_Graph_Cycle_Id) return Natural;
981 pragma Inline (Invocation_Edge_Count);
982 -- Obtain the number of invocation edges in cycle Cycle of library
987 Cycle : Library_Graph_Cycle_Id) return Library_Graph_Cycle_Kind;
988 pragma Inline (Kind);
989 -- Obtain the nature of cycle Cycle of library graph G
993 Cycle : Library_Graph_Cycle_Id) return Natural;
994 pragma Inline (Length);
995 -- Obtain the length of cycle Cycle of library graph G
1001 function Complementary_Vertex
1003 Vertex : Library_Graph_Vertex_Id;
1004 Force_Complement : Boolean) return Library_Graph_Vertex_Id;
1005 pragma Inline (Complementary_Vertex);
1006 -- Obtain the complementary vertex of vertex Vertex of library graph G
1009 -- * If Vertex is the spec of an Elaborate_Body pair, return the body
1010 -- * If Vertex is the body of an Elaborate_Body pair, return the spec
1012 -- This behavior can be forced by setting flag Force_Complement to True.
1014 function Contains_Elaborate_All_Edge
1016 Cycle : Library_Graph_Cycle_Id) return Boolean;
1017 pragma Inline (Contains_Elaborate_All_Edge);
1018 -- Determine whether cycle Cycle of library graph G contains an
1019 -- Elaborate_All edge.
1021 function Contains_Static_Successor_Edge
1023 Cycle : Library_Graph_Cycle_Id) return Boolean;
1024 pragma Inline (Contains_Static_Successor_Edge);
1025 -- Determine whether cycle Cycle of library graph G contains an edge
1026 -- where the successor was compiled using the static model.
1028 function Contains_Task_Activation
1030 Cycle : Library_Graph_Cycle_Id) return Boolean;
1031 pragma Inline (Contains_Task_Activation);
1032 -- Determine whether cycle Cycle of library graph G contains an
1033 -- invocation edge where the path it represents involves a task
1036 function Has_Elaborate_All_Cycle (G : Library_Graph) return Boolean;
1037 pragma Inline (Has_Elaborate_All_Cycle);
1038 -- Determine whether library graph G contains a cycle involving pragma
1041 function Has_No_Elaboration_Code
1043 Vertex : Library_Graph_Vertex_Id) return Boolean;
1044 pragma Inline (Has_No_Elaboration_Code);
1045 -- Determine whether vertex Vertex of library graph G represents a unit
1046 -- that lacks elaboration code.
1048 function In_Same_Component
1050 Left : Library_Graph_Vertex_Id;
1051 Right : Library_Graph_Vertex_Id) return Boolean;
1052 pragma Inline (In_Same_Component);
1053 -- Determine whether vertices Left and Right of library graph G reside
1054 -- in the same component.
1058 Vertex : Library_Graph_Vertex_Id) return Boolean;
1059 pragma Inline (Is_Body);
1060 -- Determine whether vertex Vertex of library graph G denotes a body
1062 function Is_Body_Of_Spec_With_Elaborate_Body
1064 Vertex : Library_Graph_Vertex_Id) return Boolean;
1065 pragma Inline (Is_Body_Of_Spec_With_Elaborate_Body);
1066 -- Determine whether vertex Vertex of library graph G denotes a body
1067 -- with a corresponding spec, and the spec has pragma Elaborate_Body.
1069 function Is_Body_With_Spec
1071 Vertex : Library_Graph_Vertex_Id) return Boolean;
1072 pragma Inline (Is_Body_With_Spec);
1073 -- Determine whether vertex Vertex of library graph G denotes a body
1074 -- with a corresponding spec.
1076 function Is_Dynamically_Elaborated
1078 Vertex : Library_Graph_Vertex_Id) return Boolean;
1079 pragma Inline (Is_Dynamically_Elaborated);
1080 -- Determine whether vertex Vertex of library graph G was compiled
1081 -- using the dynamic model.
1083 function Is_Elaborable_Component
1085 Comp : Component_Id) return Boolean;
1086 pragma Inline (Is_Elaborable_Component);
1087 -- Determine whether component Comp of library graph G is not waiting on
1088 -- any predecessors, and can thus be elaborated.
1090 function Is_Elaborable_Vertex
1092 Vertex : Library_Graph_Vertex_Id) return Boolean;
1093 pragma Inline (Is_Elaborable_Vertex);
1094 -- Determine whether vertex Vertex of library graph G is not waiting on
1095 -- any predecessors, and can thus be elaborated.
1097 function Is_Elaborate_All_Edge
1099 Edge : Library_Graph_Edge_Id) return Boolean;
1100 pragma Inline (Is_Elaborate_All_Edge);
1101 -- Determine whether edge Edge of library graph G is an edge whose
1102 -- predecessor is subject to pragma Elaborate_All.
1104 function Is_Elaborate_Body_Edge
1106 Edge : Library_Graph_Edge_Id) return Boolean;
1107 pragma Inline (Is_Elaborate_Body_Edge);
1108 -- Determine whether edge Edge of library graph G has a successor
1109 -- that is either a spec subject to pragma Elaborate_Body, or a body
1110 -- that completes such a spec.
1112 function Is_Elaborate_Edge
1114 Edge : Library_Graph_Edge_Id) return Boolean;
1115 pragma Inline (Is_Elaborate_Edge);
1116 -- Determine whether edge Edge of library graph G is an edge whose
1117 -- predecessor is subject to pragma Elaborate.
1119 function Is_Elaborate_Body_Pair
1121 Spec_Vertex : Library_Graph_Vertex_Id;
1122 Body_Vertex : Library_Graph_Vertex_Id) return Boolean;
1123 pragma Inline (Is_Elaborate_Body_Pair);
1124 -- Determine whether vertices Spec_Vertex and Body_Vertex of library
1125 -- graph G denote a spec subject to Elaborate_Body and its completing
1128 function Is_Forced_Edge
1130 Edge : Library_Graph_Edge_Id) return Boolean;
1131 pragma Inline (Is_Forced_Edge);
1132 -- Determine whether edge Edge of library graph G is a byproduct of the
1133 -- forced-elaboration-order file.
1135 function Is_Internal_Unit
1137 Vertex : Library_Graph_Vertex_Id) return Boolean;
1138 pragma Inline (Is_Internal_Unit);
1139 -- Determine whether vertex Vertex of library graph G denotes an
1142 function Is_Invocation_Edge
1144 Edge : Library_Graph_Edge_Id) return Boolean;
1145 pragma Inline (Is_Invocation_Edge);
1146 -- Determine whether edge Edge of library graph G came from the
1147 -- traversal of the invocation graph.
1149 function Is_Predefined_Unit
1151 Vertex : Library_Graph_Vertex_Id) return Boolean;
1152 pragma Inline (Is_Predefined_Unit);
1153 -- Determine whether vertex Vertex of library graph G denotes a
1156 function Is_Preelaborated_Unit
1158 Vertex : Library_Graph_Vertex_Id) return Boolean;
1159 pragma Inline (Is_Preelaborated_Unit);
1160 -- Determine whether vertex Vertex of library graph G denotes a unit
1161 -- subject to pragma Pure or Preelaborable.
1165 Vertex : Library_Graph_Vertex_Id) return Boolean;
1166 pragma Inline (Is_Spec);
1167 -- Determine whether vertex Vertex of library graph G denotes a spec
1169 function Is_Spec_Before_Body_Edge
1171 Edge : Library_Graph_Edge_Id) return Boolean;
1172 pragma Inline (Is_Spec_Before_Body_Edge);
1173 -- Determine whether edge Edge of library graph G links a predecessor
1174 -- spec and a successor body belonging to the same unit.
1176 function Is_Spec_With_Body
1178 Vertex : Library_Graph_Vertex_Id) return Boolean;
1179 pragma Inline (Is_Spec_With_Body);
1180 -- Determine whether vertex Vertex of library graph G denotes a spec
1181 -- with a corresponding body.
1183 function Is_Spec_With_Elaborate_Body
1185 Vertex : Library_Graph_Vertex_Id) return Boolean;
1186 pragma Inline (Is_Spec_With_Elaborate_Body);
1187 -- Determine whether vertex Vertex of library graph G denotes a spec
1188 -- with a corresponding body, and is subject to pragma Elaborate_Body.
1190 function Is_Weakly_Elaborable_Vertex
1192 Vertex : Library_Graph_Vertex_Id) return Boolean;
1193 pragma Inline (Is_Weakly_Elaborable_Vertex);
1194 -- Determine whether vertex Vertex of library graph G is waiting on
1195 -- weak predecessors only, in which case it can be elaborated assuming
1196 -- that the weak edges will not be exercised at elaboration time.
1198 function Is_With_Edge
1200 Edge : Library_Graph_Edge_Id) return Boolean;
1201 pragma Inline (Is_With_Edge);
1202 -- Determine whether edge Edge of library graph G is the result of a
1203 -- with dependency between its successor and predecessor.
1205 function Needs_Elaboration
1207 Vertex : Library_Graph_Vertex_Id) return Boolean;
1208 pragma Inline (Needs_Elaboration);
1209 -- Determine whether vertex Vertex of library graph G represents a unit
1210 -- that needs to be elaborated.
1212 function Proper_Body
1214 Vertex : Library_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
1215 pragma Inline (Proper_Body);
1216 -- Obtain the body of vertex Vertex of library graph G
1218 function Proper_Spec
1220 Vertex : Library_Graph_Vertex_Id) return Library_Graph_Vertex_Id;
1221 pragma Inline (Proper_Spec);
1222 -- Obtain the spec of vertex Vertex of library graph G
1228 function Library_Graph_Edge_Count
1230 Kind : Library_Graph_Edge_Kind) return Natural;
1231 pragma Inline (Library_Graph_Edge_Count);
1232 -- Obtain the total number of edges of kind Kind in library graph G
1234 function Number_Of_Component_Vertices
1236 Comp : Component_Id) return Natural;
1237 pragma Inline (Number_Of_Component_Vertices);
1238 -- Obtain the total number of vertices component Comp of library graph
1241 function Number_Of_Components (G : Library_Graph) return Natural;
1242 pragma Inline (Number_Of_Components);
1243 -- Obtain the total number of components in library graph G
1245 function Number_Of_Cycles (G : Library_Graph) return Natural;
1246 pragma Inline (Number_Of_Cycles);
1247 -- Obtain the total number of cycles in library graph G
1249 function Number_Of_Edges (G : Library_Graph) return Natural;
1250 pragma Inline (Number_Of_Edges);
1251 -- Obtain the total number of edges in library graph G
1253 function Number_Of_Edges_To_Successors
1255 Vertex : Library_Graph_Vertex_Id) return Natural;
1256 pragma Inline (Number_Of_Edges_To_Successors);
1257 -- Obtain the total number of edges to successors vertex Vertex of
1258 -- library graph G has.
1260 function Number_Of_Vertices (G : Library_Graph) return Natural;
1261 pragma Inline (Number_Of_Vertices);
1262 -- Obtain the total number of vertices in library graph G
1268 -- The following type represents an iterator over all cycles of a
1271 type All_Cycle_Iterator is private;
1273 function Has_Next (Iter : All_Cycle_Iterator) return Boolean;
1274 pragma Inline (Has_Next);
1275 -- Determine whether iterator Iter has more cycles to examine
1277 function Iterate_All_Cycles
1278 (G : Library_Graph) return All_Cycle_Iterator;
1279 pragma Inline (Iterate_All_Cycles);
1280 -- Obtain an iterator over all cycles of library graph G
1283 (Iter : in out All_Cycle_Iterator;
1284 Cycle : out Library_Graph_Cycle_Id);
1285 pragma Inline (Next);
1286 -- Return the current cycle referenced by iterator Iter and advance to
1287 -- the next available cycle.
1289 -- The following type represents an iterator over all edges of a library
1292 type All_Edge_Iterator is private;
1294 function Has_Next (Iter : All_Edge_Iterator) return Boolean;
1295 pragma Inline (Has_Next);
1296 -- Determine whether iterator Iter has more edges to examine
1298 function Iterate_All_Edges (G : Library_Graph) return All_Edge_Iterator;
1299 pragma Inline (Iterate_All_Edges);
1300 -- Obtain an iterator over all edges of library graph G
1303 (Iter : in out All_Edge_Iterator;
1304 Edge : out Library_Graph_Edge_Id);
1305 pragma Inline (Next);
1306 -- Return the current edge referenced by iterator Iter and advance to
1307 -- the next available edge.
1309 -- The following type represents an iterator over all vertices of a
1312 type All_Vertex_Iterator is private;
1314 function Has_Next (Iter : All_Vertex_Iterator) return Boolean;
1315 pragma Inline (Has_Next);
1316 -- Determine whether iterator Iter has more vertices to examine
1318 function Iterate_All_Vertices
1319 (G : Library_Graph) return All_Vertex_Iterator;
1320 pragma Inline (Iterate_All_Vertices);
1321 -- Obtain an iterator over all vertices of library graph G
1324 (Iter : in out All_Vertex_Iterator;
1325 Vertex : out Library_Graph_Vertex_Id);
1326 pragma Inline (Next);
1327 -- Return the current vertex referenced by iterator Iter and advance
1328 -- to the next available vertex.
1330 -- The following type represents an iterator over all components of a
1333 type Component_Iterator is private;
1335 function Has_Next (Iter : Component_Iterator) return Boolean;
1336 pragma Inline (Has_Next);
1337 -- Determine whether iterator Iter has more components to examine
1339 function Iterate_Components
1340 (G : Library_Graph) return Component_Iterator;
1341 pragma Inline (Iterate_Components);
1342 -- Obtain an iterator over all components of library graph G
1345 (Iter : in out Component_Iterator;
1346 Comp : out Component_Id);
1347 pragma Inline (Next);
1348 -- Return the current component referenced by iterator Iter and advance
1349 -- to the next available component.
1351 -- The following type represents an iterator over all vertices of a
1354 type Component_Vertex_Iterator is private;
1356 function Has_Next (Iter : Component_Vertex_Iterator) return Boolean;
1357 pragma Inline (Has_Next);
1358 -- Determine whether iterator Iter has more vertices to examine
1360 function Iterate_Component_Vertices
1362 Comp : Component_Id) return Component_Vertex_Iterator;
1363 pragma Inline (Iterate_Component_Vertices);
1364 -- Obtain an iterator over all vertices of component Comp of library
1368 (Iter : in out Component_Vertex_Iterator;
1369 Vertex : out Library_Graph_Vertex_Id);
1370 pragma Inline (Next);
1371 -- Return the current vertex referenced by iterator Iter and advance
1372 -- to the next available vertex.
1374 -- The following type represents an iterator over all edges that form a
1377 type Edges_Of_Cycle_Iterator is private;
1379 function Has_Next (Iter : Edges_Of_Cycle_Iterator) return Boolean;
1380 pragma Inline (Has_Next);
1381 -- Determine whether iterator Iter has more edges to examine
1383 function Iterate_Edges_Of_Cycle
1385 Cycle : Library_Graph_Cycle_Id) return Edges_Of_Cycle_Iterator;
1386 pragma Inline (Iterate_Edges_Of_Cycle);
1387 -- Obtain an iterator over all edges that form cycle Cycle of library
1391 (Iter : in out Edges_Of_Cycle_Iterator;
1392 Edge : out Library_Graph_Edge_Id);
1393 pragma Inline (Next);
1394 -- Return the current edge referenced by iterator Iter and advance to
1395 -- the next available edge.
1397 -- The following type represents an iterator over all edges that reach
1398 -- successors starting from a particular predecessor vertex.
1400 type Edges_To_Successors_Iterator is private;
1402 function Has_Next (Iter : Edges_To_Successors_Iterator) return Boolean;
1403 pragma Inline (Has_Next);
1404 -- Determine whether iterator Iter has more edges to examine
1406 function Iterate_Edges_To_Successors
1408 Vertex : Library_Graph_Vertex_Id) return Edges_To_Successors_Iterator;
1409 pragma Inline (Iterate_Edges_To_Successors);
1410 -- Obtain an iterator over all edges to successors with predecessor
1411 -- vertex Vertex of library graph G.
1414 (Iter : in out Edges_To_Successors_Iterator;
1415 Edge : out Library_Graph_Edge_Id);
1416 pragma Inline (Next);
1417 -- Return the current edge referenced by iterator Iter and advance to
1418 -- the next available edge.
1426 -- The following type represents the attributes of a library graph
1429 type Library_Graph_Vertex_Attributes is record
1430 Corresponding_Item : Library_Graph_Vertex_Id :=
1431 No_Library_Graph_Vertex;
1432 -- The reference to the corresponding spec or body. This attribute is
1435 -- * If predicate Is_Body_With_Spec is True, the reference denotes
1436 -- the corresponding spec.
1438 -- * If predicate Is_Spec_With_Body is True, the reference denotes
1439 -- the corresponding body.
1441 -- * Otherwise the attribute remains empty.
1443 In_Elaboration_Order : Boolean := False;
1444 -- Set when this vertex is elaborated
1446 Pending_Strong_Predecessors : Natural := 0;
1447 -- The number of pending strong predecessor vertices this vertex must
1448 -- wait on before it can be elaborated.
1450 Pending_Weak_Predecessors : Natural := 0;
1451 -- The number of weak predecessor vertices this vertex must wait on
1452 -- before it can be elaborated.
1454 Unit : Unit_Id := No_Unit_Id;
1455 -- The reference to unit this vertex represents
1458 No_Library_Graph_Vertex_Attributes :
1459 constant Library_Graph_Vertex_Attributes :=
1460 (Corresponding_Item => No_Library_Graph_Vertex,
1461 In_Elaboration_Order => False,
1462 Pending_Strong_Predecessors => 0,
1463 Pending_Weak_Predecessors => 0,
1464 Unit => No_Unit_Id);
1466 procedure Destroy_Library_Graph_Vertex_Attributes
1467 (Attrs : in out Library_Graph_Vertex_Attributes);
1468 pragma Inline (Destroy_Library_Graph_Vertex_Attributes);
1469 -- Destroy the contents of attributes Attrs
1471 package LGV_Tables is new Dynamic_Hash_Tables
1472 (Key_Type => Library_Graph_Vertex_Id,
1473 Value_Type => Library_Graph_Vertex_Attributes,
1474 No_Value => No_Library_Graph_Vertex_Attributes,
1475 Expansion_Threshold => 1.5,
1476 Expansion_Factor => 2,
1477 Compression_Threshold => 0.3,
1478 Compression_Factor => 2,
1480 Destroy_Value => Destroy_Library_Graph_Vertex_Attributes,
1481 Hash => Hash_Library_Graph_Vertex);
1487 -- The following type represents the attributes of a library graph edge
1489 type Library_Graph_Edge_Attributes is record
1490 Activates_Task : Boolean := False;
1491 -- Set for an invocation edge, where at least one of the paths the
1492 -- edge represents activates a task.
1494 Kind : Library_Graph_Edge_Kind := No_Edge;
1495 -- The nature of the library graph edge
1498 No_Library_Graph_Edge_Attributes :
1499 constant Library_Graph_Edge_Attributes :=
1500 (Activates_Task => False,
1503 procedure Destroy_Library_Graph_Edge_Attributes
1504 (Attrs : in out Library_Graph_Edge_Attributes);
1505 pragma Inline (Destroy_Library_Graph_Edge_Attributes);
1506 -- Destroy the contents of attributes Attrs
1508 package LGE_Tables is new Dynamic_Hash_Tables
1509 (Key_Type => Library_Graph_Edge_Id,
1510 Value_Type => Library_Graph_Edge_Attributes,
1511 No_Value => No_Library_Graph_Edge_Attributes,
1512 Expansion_Threshold => 1.5,
1513 Expansion_Factor => 2,
1514 Compression_Threshold => 0.3,
1515 Compression_Factor => 2,
1517 Destroy_Value => Destroy_Library_Graph_Edge_Attributes,
1518 Hash => Hash_Library_Graph_Edge);
1524 -- The following type represents the attributes of a component
1526 type Component_Attributes is record
1527 Pending_Strong_Predecessors : Natural := 0;
1528 -- The number of pending strong predecessor components this component
1529 -- must wait on before it can be elaborated.
1531 Pending_Weak_Predecessors : Natural := 0;
1532 -- The number of pending weak predecessor components this component
1533 -- must wait on before it can be elaborated.
1536 No_Component_Attributes : constant Component_Attributes :=
1537 (Pending_Strong_Predecessors => 0,
1538 Pending_Weak_Predecessors => 0);
1540 procedure Destroy_Component_Attributes
1541 (Attrs : in out Component_Attributes);
1542 pragma Inline (Destroy_Component_Attributes);
1543 -- Destroy the contents of attributes Attrs
1545 package Component_Tables is new Dynamic_Hash_Tables
1546 (Key_Type => Component_Id,
1547 Value_Type => Component_Attributes,
1548 No_Value => No_Component_Attributes,
1549 Expansion_Threshold => 1.5,
1550 Expansion_Factor => 2,
1551 Compression_Threshold => 0.3,
1552 Compression_Factor => 2,
1554 Destroy_Value => Destroy_Component_Attributes,
1555 Hash => Hash_Component);
1561 -- The following type represents the attributes of a cycle
1563 type Library_Graph_Cycle_Attributes is record
1564 Invocation_Edge_Count : Natural := 0;
1565 -- The number of invocation edges within the cycle
1567 Kind : Library_Graph_Cycle_Kind := No_Cycle_Kind;
1568 -- The nature of the cycle
1570 Path : LGE_Lists.Doubly_Linked_List := LGE_Lists.Nil;
1571 -- The path of edges that form the cycle
1574 No_Library_Graph_Cycle_Attributes :
1575 constant Library_Graph_Cycle_Attributes :=
1576 (Invocation_Edge_Count => 0,
1577 Kind => No_Cycle_Kind,
1578 Path => LGE_Lists.Nil);
1580 procedure Destroy_Library_Graph_Cycle_Attributes
1581 (Attrs : in out Library_Graph_Cycle_Attributes);
1582 pragma Inline (Destroy_Library_Graph_Cycle_Attributes);
1583 -- Destroy the contents of attributes Attrs
1585 function Hash_Library_Graph_Cycle_Attributes
1586 (Attrs : Library_Graph_Cycle_Attributes) return Bucket_Range_Type;
1587 pragma Inline (Hash_Library_Graph_Cycle_Attributes);
1588 -- Obtain the hash of key Attrs
1590 function Same_Library_Graph_Cycle_Attributes
1591 (Left : Library_Graph_Cycle_Attributes;
1592 Right : Library_Graph_Cycle_Attributes) return Boolean;
1593 pragma Inline (Same_Library_Graph_Cycle_Attributes);
1594 -- Determine whether cycle attributes Left and Right are the same
1596 package LGC_Tables is new Dynamic_Hash_Tables
1597 (Key_Type => Library_Graph_Cycle_Id,
1598 Value_Type => Library_Graph_Cycle_Attributes,
1599 No_Value => No_Library_Graph_Cycle_Attributes,
1600 Expansion_Threshold => 1.5,
1601 Expansion_Factor => 2,
1602 Compression_Threshold => 0.3,
1603 Compression_Factor => 2,
1605 Destroy_Value => Destroy_Library_Graph_Cycle_Attributes,
1606 Hash => Hash_Library_Graph_Cycle);
1608 --------------------
1609 -- Recorded edges --
1610 --------------------
1612 -- The following type represents a relation between a predecessor and
1613 -- successor vertices.
1615 type Predecessor_Successor_Relation is record
1616 Predecessor : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
1617 -- The source vertex
1619 Successor : Library_Graph_Vertex_Id := No_Library_Graph_Vertex;
1620 -- The destination vertex
1623 No_Predecessor_Successor_Relation :
1624 constant Predecessor_Successor_Relation :=
1625 (Predecessor => No_Library_Graph_Vertex,
1626 Successor => No_Library_Graph_Vertex);
1628 function Hash_Predecessor_Successor_Relation
1629 (Rel : Predecessor_Successor_Relation) return Bucket_Range_Type;
1630 pragma Inline (Hash_Predecessor_Successor_Relation);
1631 -- Obtain the hash value of key Rel
1633 package RE_Sets is new Membership_Sets
1634 (Element_Type => Predecessor_Successor_Relation,
1636 Hash => Hash_Predecessor_Successor_Relation);
1642 type Library_Graph_Edge_Counts is
1643 array (Library_Graph_Edge_Kind) of Natural;
1649 package Unit_Tables is new Dynamic_Hash_Tables
1650 (Key_Type => Unit_Id,
1651 Value_Type => Library_Graph_Vertex_Id,
1652 No_Value => No_Library_Graph_Vertex,
1653 Expansion_Threshold => 1.5,
1654 Expansion_Factor => 2,
1655 Compression_Threshold => 0.3,
1656 Compression_Factor => 2,
1658 Destroy_Value => Destroy_Library_Graph_Vertex,
1665 package DG is new Directed_Graphs
1666 (Vertex_Id => Library_Graph_Vertex_Id,
1667 No_Vertex => No_Library_Graph_Vertex,
1668 Hash_Vertex => Hash_Library_Graph_Vertex,
1670 Edge_Id => Library_Graph_Edge_Id,
1671 No_Edge => No_Library_Graph_Edge,
1672 Hash_Edge => Hash_Library_Graph_Edge,
1675 -- The following type represents the attributes of a library graph
1677 type Library_Graph_Attributes is record
1678 Component_Attributes : Component_Tables.Dynamic_Hash_Table :=
1679 Component_Tables.Nil;
1680 -- The map of component -> component attributes for all components in
1683 Counts : Library_Graph_Edge_Counts := (others => 0);
1686 Cycle_Attributes : LGC_Tables.Dynamic_Hash_Table := LGC_Tables.Nil;
1687 -- The map of cycle -> cycle attributes for all cycles in the graph
1689 Cycles : LGC_Lists.Doubly_Linked_List := LGC_Lists.Nil;
1690 -- The list of all cycles in the graph, sorted based on precedence
1692 Edge_Attributes : LGE_Tables.Dynamic_Hash_Table := LGE_Tables.Nil;
1693 -- The map of edge -> edge attributes for all edges in the graph
1695 Graph : DG.Directed_Graph := DG.Nil;
1696 -- The underlying graph describing the relations between edges and
1699 Recorded_Edges : RE_Sets.Membership_Set := RE_Sets.Nil;
1700 -- The set of recorded edges, used to prevent duplicate edges in the
1703 Unit_To_Vertex : Unit_Tables.Dynamic_Hash_Table := Unit_Tables.Nil;
1704 -- The map of unit -> vertex
1706 Vertex_Attributes : LGV_Tables.Dynamic_Hash_Table := LGV_Tables.Nil;
1707 -- The map of vertex -> vertex attributes for all vertices in the
1711 type Library_Graph is access Library_Graph_Attributes;
1712 Nil : constant Library_Graph := null;
1718 type All_Cycle_Iterator is new LGC_Lists.Iterator;
1719 type All_Edge_Iterator is new DG.All_Edge_Iterator;
1720 type All_Vertex_Iterator is new DG.All_Vertex_Iterator;
1721 type Component_Iterator is new DG.Component_Iterator;
1722 type Component_Vertex_Iterator is new DG.Component_Vertex_Iterator;
1723 type Edges_Of_Cycle_Iterator is new LGE_Lists.Iterator;
1724 type Edges_To_Successors_Iterator is new DG.Outgoing_Edge_Iterator;