1------------------------------------------------------------------------------ 2-- -- 3-- GNAT COMPILER COMPONENTS -- 4-- -- 5-- B I N D O . G R A P H S -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 2019, Free Software Foundation, Inc. -- 10-- -- 11-- GNAT is free software; you can redistribute it and/or modify it under -- 12-- terms of the GNU General Public License as published by the Free Soft- -- 13-- ware Foundation; either version 3, or (at your option) any later ver- -- 14-- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- 15-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- 16-- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -- 17-- for more details. You should have received a copy of the GNU General -- 18-- Public License distributed with GNAT; see file COPYING3. If not, go to -- 19-- http://www.gnu.org/licenses for a complete copy of the license. -- 20-- -- 21-- GNAT was originally developed by the GNAT team at New York University. -- 22-- Extensive contributions were provided by Ada Core Technologies Inc. -- 23-- -- 24------------------------------------------------------------------------------ 25 26-- For full architecture, see unit Bindo. 27 28-- The following unit defines the various graphs used in determining the 29-- elaboration order of units. 30 31with Types; use Types; 32 33with Bindo.Units; use Bindo.Units; 34 35with GNAT; use GNAT; 36with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables; 37with GNAT.Graphs; use GNAT.Graphs; 38with GNAT.Lists; use GNAT.Lists; 39with GNAT.Sets; use GNAT.Sets; 40 41package Bindo.Graphs is 42 43 --------------------------- 44 -- Invocation graph edge -- 45 --------------------------- 46 47 -- The following type denotes an invocation graph edge handle 48 49 type Invocation_Graph_Edge_Id is new Natural; 50 No_Invocation_Graph_Edge : constant Invocation_Graph_Edge_Id := 51 Invocation_Graph_Edge_Id'First; 52 First_Invocation_Graph_Edge : constant Invocation_Graph_Edge_Id := 53 No_Invocation_Graph_Edge + 1; 54 55 procedure Destroy_Invocation_Graph_Edge 56 (Edge : in out Invocation_Graph_Edge_Id); 57 pragma Inline (Destroy_Invocation_Graph_Edge); 58 -- Destroy invocation graph edge Edge 59 60 function Hash_Invocation_Graph_Edge 61 (Edge : Invocation_Graph_Edge_Id) return Bucket_Range_Type; 62 pragma Inline (Hash_Invocation_Graph_Edge); 63 -- Obtain the hash value of key Edge 64 65 function Present (Edge : Invocation_Graph_Edge_Id) return Boolean; 66 pragma Inline (Present); 67 -- Determine whether invocation graph edge Edge exists 68 69 package IGE_Lists is new Doubly_Linked_Lists 70 (Element_Type => Invocation_Graph_Edge_Id, 71 "=" => "=", 72 Destroy_Element => Destroy_Invocation_Graph_Edge); 73 74 ------------------------------ 75 -- Invocation graph vertex -- 76 ------------------------------ 77 78 -- The following type denotes an invocation graph vertex handle 79 80 type Invocation_Graph_Vertex_Id is new Natural; 81 No_Invocation_Graph_Vertex : constant Invocation_Graph_Vertex_Id := 82 Invocation_Graph_Vertex_Id'First; 83 First_Invocation_Graph_Vertex : constant Invocation_Graph_Vertex_Id := 84 No_Invocation_Graph_Vertex + 1; 85 86 function Hash_Invocation_Graph_Vertex 87 (Vertex : Invocation_Graph_Vertex_Id) return Bucket_Range_Type; 88 pragma Inline (Hash_Invocation_Graph_Vertex); 89 -- Obtain the hash value of key Vertex 90 91 function Present (Vertex : Invocation_Graph_Vertex_Id) return Boolean; 92 pragma Inline (Present); 93 -- Determine whether invocation graph vertex Vertex exists 94 95 package IGV_Sets is new Membership_Sets 96 (Element_Type => Invocation_Graph_Vertex_Id, 97 "=" => "=", 98 Hash => Hash_Invocation_Graph_Vertex); 99 100 ------------------------- 101 -- Library graph cycle -- 102 ------------------------- 103 104 type Library_Graph_Cycle_Id is new Natural; 105 No_Library_Graph_Cycle : constant Library_Graph_Cycle_Id := 106 Library_Graph_Cycle_Id'First; 107 First_Library_Graph_Cycle : constant Library_Graph_Cycle_Id := 108 No_Library_Graph_Cycle + 1; 109 110 procedure Destroy_Library_Graph_Cycle 111 (Cycle : in out Library_Graph_Cycle_Id); 112 pragma Inline (Destroy_Library_Graph_Cycle); 113 -- Destroy library graph cycle Cycle 114 115 function Hash_Library_Graph_Cycle 116 (Cycle : Library_Graph_Cycle_Id) return Bucket_Range_Type; 117 pragma Inline (Hash_Library_Graph_Cycle); 118 -- Obtain the hash value of key Cycle 119 120 function Present (Cycle : Library_Graph_Cycle_Id) return Boolean; 121 pragma Inline (Present); 122 -- Determine whether library graph cycle Cycle exists 123 124 package LGC_Lists is new Doubly_Linked_Lists 125 (Element_Type => Library_Graph_Cycle_Id, 126 "=" => "=", 127 Destroy_Element => Destroy_Library_Graph_Cycle); 128 129 ------------------------ 130 -- Library graph edge -- 131 ------------------------ 132 133 -- The following type denotes a library graph edge handle 134 135 type Library_Graph_Edge_Id is new Natural; 136 No_Library_Graph_Edge : constant Library_Graph_Edge_Id := 137 Library_Graph_Edge_Id'First; 138 First_Library_Graph_Edge : constant Library_Graph_Edge_Id := 139 No_Library_Graph_Edge + 1; 140 141 procedure Destroy_Library_Graph_Edge 142 (Edge : in out Library_Graph_Edge_Id); 143 pragma Inline (Destroy_Library_Graph_Edge); 144 -- Destroy library graph edge Edge 145 146 function Hash_Library_Graph_Edge 147 (Edge : Library_Graph_Edge_Id) return Bucket_Range_Type; 148 pragma Inline (Hash_Library_Graph_Edge); 149 -- Obtain the hash value of key Edge 150 151 function Present (Edge : Library_Graph_Edge_Id) return Boolean; 152 pragma Inline (Present); 153 -- Determine whether library graph edge Edge exists 154 155 package LGE_Lists is new Doubly_Linked_Lists 156 (Element_Type => Library_Graph_Edge_Id, 157 "=" => "=", 158 Destroy_Element => Destroy_Library_Graph_Edge); 159 160 package LGE_Sets is new Membership_Sets 161 (Element_Type => Library_Graph_Edge_Id, 162 "=" => "=", 163 Hash => Hash_Library_Graph_Edge); 164 165 -------------------------- 166 -- Library graph vertex -- 167 -------------------------- 168 169 -- The following type denotes a library graph vertex handle 170 171 type Library_Graph_Vertex_Id is new Natural; 172 No_Library_Graph_Vertex : constant Library_Graph_Vertex_Id := 173 Library_Graph_Vertex_Id'First; 174 First_Library_Graph_Vertex : constant Library_Graph_Vertex_Id := 175 No_Library_Graph_Vertex + 1; 176 177 procedure Destroy_Library_Graph_Vertex 178 (Vertex : in out Library_Graph_Vertex_Id); 179 pragma Inline (Destroy_Library_Graph_Vertex); 180 -- Destroy library graph vertex Vertex 181 182 function Hash_Library_Graph_Vertex 183 (Vertex : Library_Graph_Vertex_Id) return Bucket_Range_Type; 184 pragma Inline (Hash_Library_Graph_Vertex); 185 -- Obtain the hash value of key Vertex 186 187 function Present (Vertex : Library_Graph_Vertex_Id) return Boolean; 188 pragma Inline (Present); 189 -- Determine whether library graph vertex Vertex exists 190 191 package LGV_Lists is new Doubly_Linked_Lists 192 (Element_Type => Library_Graph_Vertex_Id, 193 "=" => "=", 194 Destroy_Element => Destroy_Library_Graph_Vertex); 195 196 package LGV_Sets is new Membership_Sets 197 (Element_Type => Library_Graph_Vertex_Id, 198 "=" => "=", 199 Hash => Hash_Library_Graph_Vertex); 200 201 ----------------------- 202 -- Invocation_Graphs -- 203 ----------------------- 204 205 package Invocation_Graphs is 206 207 ----------- 208 -- Graph -- 209 ----------- 210 211 -- The following type denotes an invocation graph handle. Each instance 212 -- must be created using routine Create. 213 214 type Invocation_Graph is private; 215 Nil : constant Invocation_Graph; 216 217 ---------------------- 218 -- Graph operations -- 219 ---------------------- 220 221 procedure Add_Edge 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 229 -- describes. 230 231 procedure Add_Vertex 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 241 -- declared. 242 243 function Create 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. 249 250 procedure Destroy (G : in out Invocation_Graph); 251 pragma Inline (Destroy); 252 -- Destroy the contents of invocation graph G, rendering it unusable 253 254 function Present (G : Invocation_Graph) return Boolean; 255 pragma Inline (Present); 256 -- Determine whether invocation graph G exists 257 258 ----------------------- 259 -- Vertex attributes -- 260 ----------------------- 261 262 function Body_Vertex 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 268 -- declared. 269 270 function Column 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. 276 277 function Construct 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 282 -- describes. 283 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 289 -- IS_Id. 290 291 function Line 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. 297 298 function Name 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 303 -- describes. 304 305 function Spec_Vertex 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 311 -- declared. 312 313 --------------------- 314 -- Edge attributes -- 315 --------------------- 316 317 function Extra 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. 323 324 function Kind 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 329 330 function Relation 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 335 336 function Target 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 341 342 ---------------- 343 -- Statistics -- 344 ---------------- 345 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 351 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 355 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. 362 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 367 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 371 372 --------------- 373 -- Iterators -- 374 --------------- 375 376 -- The following type represents an iterator over all edges of an 377 -- invocation graph. 378 379 type All_Edge_Iterator is private; 380 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 384 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 389 390 procedure Next 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. 396 397 -- The following type represents an iterator over all vertices of an 398 -- invocation graph. 399 400 type All_Vertex_Iterator is private; 401 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 405 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 410 411 procedure Next 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. 417 418 -- The following type represents an iterator over all edges that reach 419 -- targets starting from a particular source vertex. 420 421 type Edges_To_Targets_Iterator is private; 422 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 426 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. 433 434 procedure Next 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. 440 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. 444 445 type Elaboration_Root_Iterator is private; 446 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 450 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 455 456 procedure Next 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. 462 463 private 464 465 -------------- 466 -- Vertices -- 467 -------------- 468 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 473 474 -- The following type represents the attributes of an invocation graph 475 -- vertex. 476 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 480 -- vertex resides. 481 482 Construct : Invocation_Construct_Id := No_Invocation_Construct; 483 -- Reference to the invocation construct this vertex represents 484 485 Spec_Vertex : Library_Graph_Vertex_Id := No_Library_Graph_Vertex; 486 -- Reference to the library graph vertex where the spec of this 487 -- vertex resides. 488 end record; 489 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); 495 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 500 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, 509 "=" => "=", 510 Destroy_Value => Destroy_Invocation_Graph_Vertex_Attributes, 511 Hash => Hash_Invocation_Graph_Vertex); 512 513 ----------- 514 -- Edges -- 515 ----------- 516 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 521 522 -- The following type represents the attributes of an invocation graph 523 -- edge. 524 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 528 end record; 529 530 No_Invocation_Graph_Edge_Attributes : 531 constant Invocation_Graph_Edge_Attributes := 532 (Relation => No_Invocation_Relation); 533 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 538 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, 547 "=" => "=", 548 Destroy_Value => Destroy_Invocation_Graph_Edge_Attributes, 549 Hash => Hash_Invocation_Graph_Edge); 550 551 --------------- 552 -- Relations -- 553 --------------- 554 555 -- The following type represents a relation between a source and target 556 -- vertices. 557 558 type Source_Target_Relation is record 559 Source : Invocation_Graph_Vertex_Id := No_Invocation_Graph_Vertex; 560 -- The source vertex 561 562 Target : Invocation_Graph_Vertex_Id := No_Invocation_Graph_Vertex; 563 -- The destination vertex 564 end record; 565 566 No_Source_Target_Relation : 567 constant Source_Target_Relation := 568 (Source => No_Invocation_Graph_Vertex, 569 Target => No_Invocation_Graph_Vertex); 570 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 575 576 package Relation_Sets is new Membership_Sets 577 (Element_Type => Source_Target_Relation, 578 "=" => "=", 579 Hash => Hash_Source_Target_Relation); 580 581 ---------------- 582 -- Statistics -- 583 ---------------- 584 585 type Invocation_Graph_Edge_Counts is array (Invocation_Kind) of Natural; 586 587 ---------------- 588 -- Signatures -- 589 ---------------- 590 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 595 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, 604 "=" => "=", 605 Destroy_Value => Destroy_Invocation_Graph_Vertex, 606 Hash => Hash_Invocation_Signature); 607 608 ----------------------- 609 -- Elaboration roots -- 610 ----------------------- 611 612 package IGV_Sets is new Membership_Sets 613 (Element_Type => Invocation_Graph_Vertex_Id, 614 "=" => "=", 615 Hash => Hash_Invocation_Graph_Vertex); 616 617 ----------- 618 -- Graph -- 619 ----------- 620 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, 625 Same_Vertex => "=", 626 Edge_id => Invocation_Graph_Edge_Id, 627 No_Edge => No_Invocation_Graph_Edge, 628 Hash_Edge => Hash_Invocation_Graph_Edge, 629 Same_Edge => "="); 630 631 -- The following type represents the attributes of an invocation graph 632 633 type Invocation_Graph_Attributes is record 634 Counts : Invocation_Graph_Edge_Counts := (others => 0); 635 -- Edge statistics 636 637 Edge_Attributes : IGE_Tables.Dynamic_Hash_Table := IGE_Tables.Nil; 638 -- The map of edge -> edge attributes for all edges in the graph 639 640 Graph : DG.Directed_Graph := DG.Nil; 641 -- The underlying graph describing the relations between edges and 642 -- vertices. 643 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. 647 648 Roots : IGV_Sets.Membership_Set := IGV_Sets.Nil; 649 -- The set of elaboration root vertices 650 651 Signature_To_Vertex : Signature_Tables.Dynamic_Hash_Table := 652 Signature_Tables.Nil; 653 -- The map of signature -> vertex 654 655 Vertex_Attributes : IGV_Tables.Dynamic_Hash_Table := IGV_Tables.Nil; 656 -- The map of vertex -> vertex attributes for all vertices in the 657 -- graph. 658 end record; 659 660 type Invocation_Graph is access Invocation_Graph_Attributes; 661 Nil : constant Invocation_Graph := null; 662 663 --------------- 664 -- Iterators -- 665 --------------- 666 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; 672 673 -------------------- 674 -- Library_Graphs -- 675 -------------------- 676 677 package Library_Graphs is 678 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. 682 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 687 -- precedence cycle. 688 689 Elaborate_Cycle, 690 -- A cycle that involves at least one Elaborate edge 691 692 Elaborate_All_Cycle, 693 -- A cycle that involves at least one Elaborate_All edge 694 695 Forced_Cycle, 696 -- A cycle that involves at least one edge which is a byproduct of 697 -- the forced-elaboration-order file. 698 699 Invocation_Cycle, 700 -- A cycle that involves at least one invocation edge. This is the 701 -- lowest precedence cycle. 702 703 No_Cycle_Kind); 704 705 -- The following type represents the various kinds of library edges 706 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. 712 713 Elaborate_Edge, 714 -- Successor withs Predecessor, and has pragma Elaborate for it 715 716 Elaborate_All_Edge, 717 -- Successor withs Predecessor, and has pragma Elaborate_All for it 718 719 Forced_Edge, 720 -- Successor is forced to with Predecessor by virtue of an existing 721 -- elaboration order provided in a file. 722 723 Invocation_Edge, 724 -- An invocation construct in unit Successor invokes a target in unit 725 -- Predecessor. 726 727 Spec_Before_Body_Edge, 728 -- Successor denotes a body, Predecessor denotes a spec 729 730 With_Edge, 731 -- Successor withs Predecessor 732 733 No_Edge); 734 735 ----------- 736 -- Graph -- 737 ----------- 738 739 -- The following type denotes a library graph handle. Each instance must 740 -- be created using routine Create. 741 742 type Library_Graph is private; 743 Nil : constant Library_Graph; 744 745 type LGE_Predicate_Ptr is access function 746 (G : Library_Graph; 747 Edge : Library_Graph_Edge_Id) return Boolean; 748 749 type LGV_Comparator_Ptr is access function 750 (G : Library_Graph; 751 Vertex : Library_Graph_Vertex_Id; 752 Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind; 753 754 type LGV_Predicate_Ptr is access function 755 (G : Library_Graph; 756 Vertex : Library_Graph_Vertex_Id) return Boolean; 757 758 ---------------------- 759 -- Graph operations -- 760 ---------------------- 761 762 procedure Add_Edge 763 (G : Library_Graph; 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. 772 773 procedure Add_Vertex 774 (G : Library_Graph; 775 U_Id : Unit_Id); 776 pragma Inline (Add_Vertex); 777 -- Create a new vertex in library graph G. U_Id is the unit the vertex 778 -- describes. 779 780 function Create 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. 786 787 procedure Destroy (G : in out Library_Graph); 788 pragma Inline (Destroy); 789 -- Destroy the contents of library graph G, rendering it unusable 790 791 procedure Find_Components (G : Library_Graph); 792 pragma Inline (Find_Components); 793 -- Find all components in library graph G 794 795 procedure Find_Cycles (G : Library_Graph); 796 pragma Inline (Find_Cycles); 797 -- Find all cycles in library graph G 798 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 803 -- library graph G. 804 805 function Present (G : Library_Graph) return Boolean; 806 pragma Inline (Present); 807 -- Determine whether library graph G exists 808 809 ----------------------- 810 -- Vertex attributes -- 811 ----------------------- 812 813 function Component 814 (G : Library_Graph; 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 818 819 function Corresponding_Item 820 (G : Library_Graph; 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. 825 826 function Corresponding_Vertex 827 (G : Library_Graph; 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 831 -- unit U_Id. 832 833 procedure Decrement_Pending_Predecessors 834 (G : Library_Graph; 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 840 -- elaborated. 841 842 function File_Name 843 (G : Library_Graph; 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 847 -- resides. 848 849 function In_Elaboration_Order 850 (G : Library_Graph; 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. 855 856 function Invocation_Graph_Encoding 857 (G : Library_Graph; 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 863 -- library graph G. 864 865 function Name 866 (G : Library_Graph; 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 870 -- represents. 871 872 procedure Pending_Predecessors_For_Elaboration 873 (G : Library_Graph; 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. 882 883 function Pending_Strong_Predecessors 884 (G : Library_Graph; 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. 889 890 function Pending_Weak_Predecessors 891 (G : Library_Graph; 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. 896 897 procedure Set_Corresponding_Item 898 (G : Library_Graph; 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. 904 905 procedure Set_In_Elaboration_Order 906 (G : Library_Graph; 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. 912 913 function Unit 914 (G : Library_Graph; 915 Vertex : Library_Graph_Vertex_Id) return Unit_Id; 916 pragma Inline (Unit); 917 -- Obtain the unit vertex Vertex of library graph G represents 918 919 --------------------- 920 -- Edge attributes -- 921 --------------------- 922 923 function Activates_Task 924 (G : Library_Graph; 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 928 929 function Kind 930 (G : Library_Graph; 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 934 935 function Predecessor 936 (G : Library_Graph; 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 940 941 function Successor 942 (G : Library_Graph; 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 946 947 -------------------------- 948 -- Component attributes -- 949 -------------------------- 950 951 procedure Decrement_Pending_Predecessors 952 (G : Library_Graph; 953 Comp : Component_Id; 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 958 -- elaborated. 959 960 function Pending_Strong_Predecessors 961 (G : Library_Graph; 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. 966 967 function Pending_Weak_Predecessors 968 (G : Library_Graph; 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. 973 974 ---------------------- 975 -- Cycle attributes -- 976 ---------------------- 977 978 function Invocation_Edge_Count 979 (G : Library_Graph; 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 983 -- graph G. 984 985 function Kind 986 (G : Library_Graph; 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 990 991 function Length 992 (G : Library_Graph; 993 Cycle : Library_Graph_Cycle_Id) return Natural; 994 pragma Inline (Length); 995 -- Obtain the length of cycle Cycle of library graph G 996 997 --------------- 998 -- Semantics -- 999 --------------- 1000 1001 function Complementary_Vertex 1002 (G : Library_Graph; 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 1007 -- as follows: 1008 -- 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 1011 -- 1012 -- This behavior can be forced by setting flag Force_Complement to True. 1013 1014 function Contains_Elaborate_All_Edge 1015 (G : Library_Graph; 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. 1020 1021 function Contains_Static_Successor_Edge 1022 (G : Library_Graph; 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. 1027 1028 function Contains_Task_Activation 1029 (G : Library_Graph; 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 1034 -- activation. 1035 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 1039 -- Elaborate_All. 1040 1041 function Has_No_Elaboration_Code 1042 (G : Library_Graph; 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. 1047 1048 function In_Same_Component 1049 (G : Library_Graph; 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. 1055 1056 function Is_Body 1057 (G : Library_Graph; 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 1061 1062 function Is_Body_Of_Spec_With_Elaborate_Body 1063 (G : Library_Graph; 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. 1068 1069 function Is_Body_With_Spec 1070 (G : Library_Graph; 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. 1075 1076 function Is_Dynamically_Elaborated 1077 (G : Library_Graph; 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. 1082 1083 function Is_Elaborable_Component 1084 (G : Library_Graph; 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. 1089 1090 function Is_Elaborable_Vertex 1091 (G : Library_Graph; 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. 1096 1097 function Is_Elaborate_All_Edge 1098 (G : Library_Graph; 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. 1103 1104 function Is_Elaborate_Body_Edge 1105 (G : Library_Graph; 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. 1111 1112 function Is_Elaborate_Edge 1113 (G : Library_Graph; 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. 1118 1119 function Is_Elaborate_Body_Pair 1120 (G : Library_Graph; 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 1126 -- body. 1127 1128 function Is_Forced_Edge 1129 (G : Library_Graph; 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. 1134 1135 function Is_Internal_Unit 1136 (G : Library_Graph; 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 1140 -- internal unit. 1141 1142 function Is_Invocation_Edge 1143 (G : Library_Graph; 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. 1148 1149 function Is_Predefined_Unit 1150 (G : Library_Graph; 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 1154 -- predefined unit. 1155 1156 function Is_Preelaborated_Unit 1157 (G : Library_Graph; 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. 1162 1163 function Is_Spec 1164 (G : Library_Graph; 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 1168 1169 function Is_Spec_Before_Body_Edge 1170 (G : Library_Graph; 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. 1175 1176 function Is_Spec_With_Body 1177 (G : Library_Graph; 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. 1182 1183 function Is_Spec_With_Elaborate_Body 1184 (G : Library_Graph; 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. 1189 1190 function Is_Weakly_Elaborable_Vertex 1191 (G : Library_Graph; 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. 1197 1198 function Is_With_Edge 1199 (G : Library_Graph; 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. 1204 1205 function Needs_Elaboration 1206 (G : Library_Graph; 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. 1211 1212 function Proper_Body 1213 (G : Library_Graph; 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 1217 1218 function Proper_Spec 1219 (G : Library_Graph; 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 1223 1224 ---------------- 1225 -- Statistics -- 1226 ---------------- 1227 1228 function Library_Graph_Edge_Count 1229 (G : Library_Graph; 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 1233 1234 function Number_Of_Component_Vertices 1235 (G : Library_Graph; 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 1239 -- contains. 1240 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 1244 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 1248 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 1252 1253 function Number_Of_Edges_To_Successors 1254 (G : Library_Graph; 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. 1259 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 1263 1264 --------------- 1265 -- Iterators -- 1266 --------------- 1267 1268 -- The following type represents an iterator over all cycles of a 1269 -- library graph. 1270 1271 type All_Cycle_Iterator is private; 1272 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 1276 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 1281 1282 procedure Next 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. 1288 1289 -- The following type represents an iterator over all edges of a library 1290 -- graph. 1291 1292 type All_Edge_Iterator is private; 1293 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 1297 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 1301 1302 procedure Next 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. 1308 1309 -- The following type represents an iterator over all vertices of a 1310 -- library graph. 1311 1312 type All_Vertex_Iterator is private; 1313 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 1317 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 1322 1323 procedure Next 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. 1329 1330 -- The following type represents an iterator over all components of a 1331 -- library graph. 1332 1333 type Component_Iterator is private; 1334 1335 function Has_Next (Iter : Component_Iterator) return Boolean; 1336 pragma Inline (Has_Next); 1337 -- Determine whether iterator Iter has more components to examine 1338 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 1343 1344 procedure Next 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. 1350 1351 -- The following type represents an iterator over all vertices of a 1352 -- component. 1353 1354 type Component_Vertex_Iterator is private; 1355 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 1359 1360 function Iterate_Component_Vertices 1361 (G : Library_Graph; 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 1365 -- graph G. 1366 1367 procedure Next 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. 1373 1374 -- The following type represents an iterator over all edges that form a 1375 -- cycle. 1376 1377 type Edges_Of_Cycle_Iterator is private; 1378 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 1382 1383 function Iterate_Edges_Of_Cycle 1384 (G : Library_Graph; 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 1388 -- graph G. 1389 1390 procedure Next 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. 1396 1397 -- The following type represents an iterator over all edges that reach 1398 -- successors starting from a particular predecessor vertex. 1399 1400 type Edges_To_Successors_Iterator is private; 1401 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 1405 1406 function Iterate_Edges_To_Successors 1407 (G : Library_Graph; 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. 1412 1413 procedure Next 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. 1419 1420 private 1421 1422 -------------- 1423 -- Vertices -- 1424 -------------- 1425 1426 -- The following type represents the attributes of a library graph 1427 -- vertex. 1428 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 1433 -- set as follows: 1434 -- 1435 -- * If predicate Is_Body_With_Spec is True, the reference denotes 1436 -- the corresponding spec. 1437 -- 1438 -- * If predicate Is_Spec_With_Body is True, the reference denotes 1439 -- the corresponding body. 1440 -- 1441 -- * Otherwise the attribute remains empty. 1442 1443 In_Elaboration_Order : Boolean := False; 1444 -- Set when this vertex is elaborated 1445 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. 1449 1450 Pending_Weak_Predecessors : Natural := 0; 1451 -- The number of weak predecessor vertices this vertex must wait on 1452 -- before it can be elaborated. 1453 1454 Unit : Unit_Id := No_Unit_Id; 1455 -- The reference to unit this vertex represents 1456 end record; 1457 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); 1465 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 1470 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, 1479 "=" => "=", 1480 Destroy_Value => Destroy_Library_Graph_Vertex_Attributes, 1481 Hash => Hash_Library_Graph_Vertex); 1482 1483 ----------- 1484 -- Edges -- 1485 ----------- 1486 1487 -- The following type represents the attributes of a library graph edge 1488 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. 1493 1494 Kind : Library_Graph_Edge_Kind := No_Edge; 1495 -- The nature of the library graph edge 1496 end record; 1497 1498 No_Library_Graph_Edge_Attributes : 1499 constant Library_Graph_Edge_Attributes := 1500 (Activates_Task => False, 1501 Kind => No_Edge); 1502 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 1507 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, 1516 "=" => "=", 1517 Destroy_Value => Destroy_Library_Graph_Edge_Attributes, 1518 Hash => Hash_Library_Graph_Edge); 1519 1520 ---------------- 1521 -- Components -- 1522 ---------------- 1523 1524 -- The following type represents the attributes of a component 1525 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. 1530 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. 1534 end record; 1535 1536 No_Component_Attributes : constant Component_Attributes := 1537 (Pending_Strong_Predecessors => 0, 1538 Pending_Weak_Predecessors => 0); 1539 1540 procedure Destroy_Component_Attributes 1541 (Attrs : in out Component_Attributes); 1542 pragma Inline (Destroy_Component_Attributes); 1543 -- Destroy the contents of attributes Attrs 1544 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, 1553 "=" => "=", 1554 Destroy_Value => Destroy_Component_Attributes, 1555 Hash => Hash_Component); 1556 1557 ------------ 1558 -- Cycles -- 1559 ------------ 1560 1561 -- The following type represents the attributes of a cycle 1562 1563 type Library_Graph_Cycle_Attributes is record 1564 Invocation_Edge_Count : Natural := 0; 1565 -- The number of invocation edges within the cycle 1566 1567 Kind : Library_Graph_Cycle_Kind := No_Cycle_Kind; 1568 -- The nature of the cycle 1569 1570 Path : LGE_Lists.Doubly_Linked_List := LGE_Lists.Nil; 1571 -- The path of edges that form the cycle 1572 end record; 1573 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); 1579 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 1584 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 1589 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 1595 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, 1604 "=" => "=", 1605 Destroy_Value => Destroy_Library_Graph_Cycle_Attributes, 1606 Hash => Hash_Library_Graph_Cycle); 1607 1608 -------------------- 1609 -- Recorded edges -- 1610 -------------------- 1611 1612 -- The following type represents a relation between a predecessor and 1613 -- successor vertices. 1614 1615 type Predecessor_Successor_Relation is record 1616 Predecessor : Library_Graph_Vertex_Id := No_Library_Graph_Vertex; 1617 -- The source vertex 1618 1619 Successor : Library_Graph_Vertex_Id := No_Library_Graph_Vertex; 1620 -- The destination vertex 1621 end record; 1622 1623 No_Predecessor_Successor_Relation : 1624 constant Predecessor_Successor_Relation := 1625 (Predecessor => No_Library_Graph_Vertex, 1626 Successor => No_Library_Graph_Vertex); 1627 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 1632 1633 package RE_Sets is new Membership_Sets 1634 (Element_Type => Predecessor_Successor_Relation, 1635 "=" => "=", 1636 Hash => Hash_Predecessor_Successor_Relation); 1637 1638 ---------------- 1639 -- Statistics -- 1640 ---------------- 1641 1642 type Library_Graph_Edge_Counts is 1643 array (Library_Graph_Edge_Kind) of Natural; 1644 1645 ----------- 1646 -- Units -- 1647 ----------- 1648 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, 1657 "=" => "=", 1658 Destroy_Value => Destroy_Library_Graph_Vertex, 1659 Hash => Hash_Unit); 1660 1661 ----------- 1662 -- Graph -- 1663 ----------- 1664 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, 1669 Same_Vertex => "=", 1670 Edge_Id => Library_Graph_Edge_Id, 1671 No_Edge => No_Library_Graph_Edge, 1672 Hash_Edge => Hash_Library_Graph_Edge, 1673 Same_Edge => "="); 1674 1675 -- The following type represents the attributes of a library graph 1676 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 1681 -- the graph. 1682 1683 Counts : Library_Graph_Edge_Counts := (others => 0); 1684 -- Edge statistics 1685 1686 Cycle_Attributes : LGC_Tables.Dynamic_Hash_Table := LGC_Tables.Nil; 1687 -- The map of cycle -> cycle attributes for all cycles in the graph 1688 1689 Cycles : LGC_Lists.Doubly_Linked_List := LGC_Lists.Nil; 1690 -- The list of all cycles in the graph, sorted based on precedence 1691 1692 Edge_Attributes : LGE_Tables.Dynamic_Hash_Table := LGE_Tables.Nil; 1693 -- The map of edge -> edge attributes for all edges in the graph 1694 1695 Graph : DG.Directed_Graph := DG.Nil; 1696 -- The underlying graph describing the relations between edges and 1697 -- vertices. 1698 1699 Recorded_Edges : RE_Sets.Membership_Set := RE_Sets.Nil; 1700 -- The set of recorded edges, used to prevent duplicate edges in the 1701 -- graph. 1702 1703 Unit_To_Vertex : Unit_Tables.Dynamic_Hash_Table := Unit_Tables.Nil; 1704 -- The map of unit -> vertex 1705 1706 Vertex_Attributes : LGV_Tables.Dynamic_Hash_Table := LGV_Tables.Nil; 1707 -- The map of vertex -> vertex attributes for all vertices in the 1708 -- graph. 1709 end record; 1710 1711 type Library_Graph is access Library_Graph_Attributes; 1712 Nil : constant Library_Graph := null; 1713 1714 --------------- 1715 -- Iterators -- 1716 --------------- 1717 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; 1725 end Library_Graphs; 1726 1727end Bindo.Graphs; 1728