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