1------------------------------------------------------------------------------ 2-- -- 3-- GNAT COMPILER COMPONENTS -- 4-- -- 5-- S C O S -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 2009-2020, 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-- This package defines tables used to store Source Coverage Obligations. It 27-- is used by Par_SCO to build the SCO information before writing it out to 28-- the ALI file, and by Get_SCO/Put_SCO to read and write the text form that 29-- is used in the ALI file. 30 31-- WARNING: There is a C version of this package. Any changes to this 32-- source file must be properly reflected in the C header file scos.h 33 34with Namet; use Namet; 35with Table; 36with Types; use Types; 37 38package SCOs is 39 40 -- SCO information can exist in one of two forms. In the ALI file, it is 41 -- represented using a text format that is described in this specification. 42 -- Internally it is stored using two tables SCO_Table and SCO_Unit_Table, 43 -- which are also defined in this unit. 44 45 -- Par_SCO is part of the compiler. It scans the parsed source tree and 46 -- populates the internal tables. 47 48 -- Get_SCO reads the text lines in ALI format and populates the internal 49 -- tables with corresponding information. 50 51 -- Put_SCO reads the internal tables and generates text lines in the ALI 52 -- format. 53 54 -------------------- 55 -- SCO ALI Format -- 56 -------------------- 57 58 -- Source coverage obligations are generated on a unit-by-unit basis in the 59 -- ALI file, using lines that start with the identifying character C. These 60 -- lines are generated if the -gnateS switch is set. 61 62 -- Sloc Ranges 63 64 -- In several places in the SCO lines, Sloc ranges appear. These are used 65 -- to indicate the first and last Sloc of some construct in the tree and 66 -- they have the form: 67 68 -- line:col-line:col 69 70 -- Note that SCO's are generated only for generic templates, not for 71 -- generic instances (since only the first are part of the source). So 72 -- we don't need generic instantiation stuff in these line:col items. 73 74 -- SCO File headers 75 76 -- The SCO information follows the cross-reference information, so it 77 -- need not be read by tools like gnatbind, gnatmake etc. The SCO output 78 -- is divided into sections, one section for each unit for which SCO's 79 -- are generated. A SCO section has a header of the form: 80 81 -- C dependency-number filename 82 83 -- This header precedes SCO information for the unit identified by 84 -- dependency number and file name. The dependency number is the 85 -- index into the generated D lines and is ones origin (i.e. 2 = 86 -- reference to second generated D line). 87 88 -- Note that the filename here will reflect the original name if 89 -- a Source_Reference pragma was encountered (since all line number 90 -- references will be with respect to the original file). 91 92 -- Note: the filename is redundant in that it could be deduced from 93 -- the corresponding D line, but it is convenient at least for human 94 -- reading of the SCO information, and means that the SCO information 95 -- can stand on its own without needing other parts of the ALI file. 96 97 -- Statements 98 99 -- For the purpose of SCO generation, the notion of statement includes 100 -- simple statements and also the following declaration types: 101 102 -- type_declaration 103 -- subtype_declaration 104 -- object_declaration 105 -- renaming_declaration 106 -- generic_instantiation 107 108 -- and the following regions of the syntax tree: 109 110 -- the part of a case_statement from CASE up to the expression 111 -- the part of a FOR loop iteration scheme from FOR up to the 112 -- loop_parameter_specification 113 -- the part of a WHILE loop up to the condition 114 -- the part of an extended_return_statement from RETURN up to the 115 -- expression (if present) or to the return_subtype_indication (if 116 -- no expression) 117 118 -- and any pragma that occurs at a place where a statement or declaration 119 -- is allowed. 120 121 -- Statement lines 122 123 -- These lines correspond to one or more successive statements (in the 124 -- sense of the above list) which are always executed in sequence (in the 125 -- absence of exceptions or other external interruptions). 126 127 -- Entry points to such sequences are: 128 129 -- the first declaration of any declarative_part 130 -- the first statement of any sequence_of_statements that is not in a 131 -- body or block statement that has a non-empty declarative part 132 -- the first statement after a compound statement 133 -- the first statement after an EXIT, RAISE or GOTO statement 134 -- any statement with a label (the label itself is not part of the 135 -- entry point that is recorded). 136 137 -- Each entry point must appear as the first statement entry on a CS 138 -- line. Thus, if any simple statement on a CS line is known to have 139 -- been executed, then all statements that appear before it on the same 140 -- CS line are certain to also have been executed. 141 142 -- The form of a statement line in the ALI file is: 143 144 -- CS [dominance] *sloc-range [*sloc-range...] 145 146 -- where each sloc-range corresponds to a single statement, and * is 147 -- one of: 148 149 -- t type declaration 150 -- s subtype declaration 151 -- o object declaration 152 -- r renaming declaration 153 -- i generic instantiation 154 -- d any other kind of declaration 155 -- A ACCEPT statement (from ACCEPT to end of parameter profile) 156 -- C CASE statement (from CASE to end of expression) 157 -- E EXIT statement 158 -- F FOR loop (from FOR to end of iteration scheme) 159 -- I IF statement (from IF to end of condition) 160 -- P[name:] PRAGMA with the indicated name 161 -- p[name:] disabled PRAGMA with the indicated name 162 -- R extended RETURN statement 163 -- S SELECT statement 164 -- W WHILE loop statement (from WHILE to end of condition) 165 -- X body of a degenerate subprogram (null procedure or 166 -- expression function) 167 168 -- Note: for I and W, condition above is in the RM syntax sense (this 169 -- condition is a decision in SCO terminology). 170 171 -- and is omitted for all other cases 172 173 -- The optional dominance marker is of the form gives additional 174 -- information as to how the sequence of statements denoted by the CS 175 -- line can be entered: 176 177 -- >F<sloc> 178 -- sequence is entered only if the decision at <sloc> is False 179 -- >T<sloc> 180 -- sequence is entered only if the decision at <sloc> is True 181 182 -- >S<sloc> 183 -- sequence is entered only if the statement at <sloc> has been 184 -- executed 185 186 -- >E<sloc-range> 187 -- sequence is the sequence of statements for a exception_handler 188 -- with the given sloc range 189 190 -- Note: up to 6 entries can appear on a single CS line. If more than 6 191 -- entries appear in one logical statement sequence, continuation lines 192 -- are marked by Cs and appear immediately after the CS line. 193 194 -- Implementation permission: a SCO generator is permitted to emit a 195 -- narrower SLOC range for a statement if the corresponding code 196 -- generation circuitry ensures that all debug information for the code 197 -- implementing the statement will be labeled with SLOCs that fall within 198 -- that narrower range. 199 200 -- Decisions 201 202 -- Note: in the following description, logical operator includes only the 203 -- short-circuited forms and NOT (so can be only NOT, AND THEN, OR ELSE). 204 -- The reason that we can exclude AND/OR/XOR is that we expect SCO's to 205 -- be generated using the restriction No_Direct_Boolean_Operators if we 206 -- are interested in decision coverage, which does not permit the use of 207 -- AND/OR/XOR on boolean operands. These are permitted on modular integer 208 -- types, but such operations do not count as decisions in any case. If 209 -- we are generating SCO's only for simple coverage, then we are not 210 -- interested in decisions in any case. 211 212 -- Note: the reason we include NOT is for informational purposes. The 213 -- presence of NOT does not generate additional coverage obligations, 214 -- but if we know where the NOT's are, the coverage tool can generate 215 -- more accurate diagnostics on uncovered tests. 216 217 -- A top level boolean expression is a boolean expression that is not an 218 -- operand of a logical operator. 219 220 -- Decisions are either simple or complex. A simple decision is a top 221 -- level boolean expression that has only one condition and that occurs 222 -- in the context of a control structure in the source program, including 223 -- WHILE, IF, EXIT WHEN, or immediately within an Assert, Check, 224 -- Pre_Condition or Post_Condition pragma, or as the first argument of a 225 -- dyadic pragma Debug. Note that a top level boolean expression with 226 -- only one condition that occurs in any other context, for example as 227 -- right hand side of an assignment, is not considered to be a (simple) 228 -- decision. 229 230 -- A complex decision is a top level boolean expression that has more 231 -- than one condition. A complex decision may occur in any boolean 232 -- expression context. 233 234 -- So for example, if we have 235 236 -- A, B, C, D : Boolean; 237 -- function F (Arg : Boolean) return Boolean); 238 -- ... 239 -- A and then (B or else F (C and then D)) 240 241 -- There are two (complex) decisions here: 242 243 -- 1. X and then (Y or else Z) 244 245 -- where X = A, Y = B, and Z = F (C and then D) 246 247 -- 2. C and then D 248 249 -- For each decision, a decision line is generated with the form: 250 251 -- C* sloc expression 252 253 -- Here * is one of the following: 254 255 -- E decision in EXIT WHEN statement 256 -- G decision in entry guard 257 -- I decision in IF statement or if expression 258 -- P decision in pragma Assert / Check / Pre/Post_Condition 259 -- A[name] decision in aspect Pre/Post (aspect name optional) 260 -- W decision in WHILE iteration scheme 261 -- X decision in some other expression context 262 263 -- For E, G, I, P, W, sloc is the source location of the EXIT, ENTRY, IF, 264 -- PRAGMA or WHILE token, respectively 265 266 -- For A sloc is the source location of the aspect identifier 267 268 -- For X, sloc is omitted 269 270 -- The expression is a prefix polish form indicating the structure of 271 -- the decision, including logical operators and short-circuit forms. 272 -- The following is a grammar showing the structure of expression: 273 274 -- expression ::= term (if expr is not logical operator) 275 -- expression ::= &sloc term term (if expr is AND or AND THEN) 276 -- expression ::= |sloc term term (if expr is OR or OR ELSE) 277 -- expression ::= !sloc term (if expr is NOT) 278 279 -- In the last three cases, sloc is the source location of the AND, OR, 280 -- or NOT token, respectively. 281 282 -- term ::= element 283 -- term ::= expression 284 285 -- element ::= *sloc-range 286 287 -- where * is one of the following letters: 288 289 -- c condition 290 -- t true condition 291 -- f false condition 292 293 -- t/f are used to mark a condition that has been recognized by the 294 -- compiler as always being true or false. c is the normal case of 295 -- conditions whose value is not known at compile time. 296 297 -- & indicates AND THEN connecting two conditions 298 299 -- | indicates OR ELSE connecting two conditions 300 301 -- ! indicates NOT applied to the expression 302 303 -- Note that complex decisions do NOT include non-short-circuited logical 304 -- operators (AND/XOR/OR). In the context of existing coverage tools the 305 -- No_Direct_Boolean_Operators restriction is assumed, so these operators 306 -- cannot appear in the source in any case. 307 308 -- The SCO line for a decision always occurs after the CS line for the 309 -- enclosing statement. The SCO line for a nested decision always occurs 310 -- after the line for the enclosing decision. 311 312 -- Note that membership tests are considered to be a single simple 313 -- condition, and that is true even if the Ada 2005 set membership 314 -- form is used, e.g. A in (2,7,11.15). 315 316 -- Implementation permission: a SCO generator is permitted to emit a 317 -- narrower SLOC range for a condition if the corresponding code 318 -- generation circuitry ensures that all debug information for the code 319 -- evaluating the condition will be labeled with SLOCs that fall within 320 -- that narrower range. 321 322 -- Case Expressions 323 324 -- For case statements, we rely on statement coverage to make sure that 325 -- all branches of a case statement are covered, but that does not work 326 -- for case expressions, since the entire expression is contained in a 327 -- single statement. However, for complete coverage we really should be 328 -- able to check that every branch of the case statement is covered, so 329 -- we generate a SCO of the form: 330 331 -- CC sloc-range sloc-range ... 332 333 -- where sloc-range covers the range of the case expression 334 335 -- Note: up to 6 entries can appear on a single CC line. If more than 6 336 -- entries appear in one logical statement sequence, continuation lines 337 -- are marked by Cc and appear immediately after the CC line. 338 339 -- Generic instances 340 341 -- A table of all generic instantiations in the compilation is generated 342 -- whose entries have the form: 343 344 -- C i index dependency-number|sloc [enclosing] 345 346 -- Where index is the 1-based index of the entry in the table, 347 -- dependency-number and sloc indicate the source location of the 348 -- instantiation, and enclosing is the index of the enclosing 349 -- instantiation in the table (for a nested instantiation), or is 350 -- omitted for an outer instantiation. 351 352 -- Disabled pragmas 353 354 -- No SCO is generated for disabled pragmas 355 356 --------------------------------------------------------------------- 357 -- Internal table used to store Source Coverage Obligations (SCOs) -- 358 --------------------------------------------------------------------- 359 360 type Source_Location is record 361 Line : Logical_Line_Number; 362 Col : Column_Number; 363 end record; 364 365 No_Source_Location : constant Source_Location := 366 (No_Line_Number, No_Column_Number); 367 368 type SCO_Table_Entry is record 369 From : Source_Location := No_Source_Location; 370 To : Source_Location := No_Source_Location; 371 C1 : Character := ' '; 372 C2 : Character := ' '; 373 Last : Boolean := False; 374 375 Pragma_Sloc : Source_Ptr := No_Location; 376 -- For the decision SCO of a pragma, or for the decision SCO of any 377 -- expression nested in a pragma Debug/Assert/PPC, location of PRAGMA 378 -- token (used for control of SCO output, value not recorded in ALI 379 -- file). Similarly, for the decision SCO of an aspect, or for the 380 -- decision SCO of any expression nested in an aspect, location of 381 -- aspect identifier token. 382 383 Pragma_Aspect_Name : Name_Id := No_Name; 384 -- For the SCO for a pragma/aspect, gives the pragma/apsect name 385 end record; 386 387 package SCO_Table is new Table.Table ( 388 Table_Component_Type => SCO_Table_Entry, 389 Table_Index_Type => Nat, 390 Table_Low_Bound => 1, 391 Table_Initial => 500, 392 Table_Increment => 300, 393 Table_Name => "Table"); 394 395 Is_Decision : constant array (Character) of Boolean := 396 ('E' | 'G' | 'I' | 'P' | 'a' | 'A' | 'W' | 'X' => True, 397 others => False); 398 -- Indicates which C1 values correspond to decisions 399 400 -- The SCO_Table_Entry values appear as follows: 401 402 -- Statements 403 -- C1 = 'S' 404 -- C2 = statement type code to appear on CS line (or ' ' if none) 405 -- From = starting source location 406 -- To = ending source location 407 -- Last = False for all but the last entry, True for last entry 408 409 -- Note: successive statements (possibly interspersed with entries of 410 -- other kinds, that are ignored for this purpose), starting with one 411 -- labeled with C1 = 'S', up to and including the first one labeled with 412 -- Last = True, indicate the sequence to be output for a sequence of 413 -- statements on a single CS line (possibly followed by Cs continuation 414 -- lines). 415 416 -- Note: for a pragma that may be disabled (Debug, Assert, PPC, Check), 417 -- the entry is initially created with C2 = 'p', to mark it as disabled. 418 -- Later on during semantic analysis, if the pragma is enabled, 419 -- Set_SCO_Pragma_Enabled changes C2 to 'P' to cause the entry to be 420 -- emitted in Put_SCOs. 421 422 -- Dominance marker 423 -- C1 = '>' 424 -- C2 = 'F'/'T'/'S'/'E' 425 -- From = Decision/statement sloc ('F'/'T'/'S'), 426 -- handler first sloc ('E') 427 -- To = No_Source_Location ('F'/'T'/'S'), handler last sloc ('E') 428 429 -- Note: A dominance marker is always followed by a statement entry 430 431 -- Decision (EXIT/entry guard/IF/WHILE) 432 -- C1 = 'E'/'G'/'I'/'W' (for EXIT/entry Guard/IF/WHILE) 433 -- C2 = ' ' 434 -- From = EXIT/ENTRY/IF/WHILE token 435 -- To = No_Source_Location 436 -- Last = unused 437 438 -- Decision (PRAGMA) 439 -- C1 = 'P' 440 -- C2 = ' ' 441 -- From = PRAGMA token 442 -- To = No_Source_Location 443 -- Last = unused 444 445 -- Note: when the parse tree is first scanned, we unconditionally build a 446 -- pragma decision entry for any decision in a pragma (here as always in 447 -- SCO contexts, the only pragmas with decisions are Assert, Check, 448 -- dyadic Debug, Precondition and Postcondition). These entries will 449 -- be omitted in output if the pragma is disabled (see comments for 450 -- statement entries): this filtering is achieved during the second pass 451 -- of SCO generation (Par_SCO.SCO_Record_Filtered). 452 453 -- Decision (ASPECT) 454 -- C1 = 'A' 455 -- C2 = ' ' 456 -- From = aspect identifier 457 -- To = No_Source_Location 458 -- Last = unused 459 460 -- Note: when the parse tree is first scanned, we unconditionally build a 461 -- pragma decision entry for any decision in an aspect (Pre/Post/ 462 -- [Type_]Invariant/[Static_|Dynamic_]Predicate). Entries for disabled 463 -- Pre/Post aspects will be omitted from output. 464 465 -- Decision (Expression) 466 -- C1 = 'X' 467 -- C2 = ' ' 468 -- From = No_Source_Location 469 -- To = No_Source_Location 470 -- Last = unused 471 472 -- Operator 473 -- C1 = '!', '&', '|' 474 -- C2 = ' '/'?'/ (Logical operator/Putative one) 475 -- From = location of NOT/AND/OR token 476 -- To = No_Source_Location 477 -- Last = False 478 479 -- Element (condition) 480 -- C1 = ' ' 481 -- C2 = 'c', 't', or 'f' (condition/true/false) 482 -- From = starting source location 483 -- To = ending source location 484 -- Last = False for all but the last entry, True for last entry 485 486 -- Note: the sequence starting with a decision, and continuing with 487 -- operators and elements up to and including the first one labeled with 488 -- Last = True, indicate the sequence to be output on one decision line. 489 490 ---------------- 491 -- Unit Table -- 492 ---------------- 493 494 -- This table keeps track of the units and the corresponding starting and 495 -- ending indexes (From, To) in the SCO table. Note that entry zero is 496 -- present but unused, it is for convenience in calling the sort routine. 497 -- Thus the lower bound for real entries is 1. 498 499 type SCO_Unit_Index is new Int; 500 -- Used to index values in this table. Values start at 1 and are assigned 501 -- sequentially as entries are constructed. 502 503 Missing_Dep_Num : constant Nat := 0; 504 -- Represents a dependency number for a dependency that is ignored. SCO 505 -- information consumers use this to strip units that must be kept out of 506 -- the coverage analysis. 507 508 type SCO_Unit_Table_Entry is record 509 File_Name : String_Ptr; 510 -- Pointer to file name in ALI file 511 512 File_Index : Source_File_Index; 513 -- Index for the source file 514 515 Dep_Num : Nat; 516 -- Dependency number in ALI file. This is a positive number when the 517 -- dependency is actually available in the context, it is 518 -- Missing_Dep_Num otherwise. 519 520 From : Nat; 521 -- Starting index in SCO_Table of SCO information for this unit 522 523 To : Nat; 524 -- Ending index in SCO_Table of SCO information for this unit 525 526 -- Warning: SCOs generation (in Par_SCO) is done in two passes, which 527 -- communicate through an intermediate table (Par_SCO.SCO_Raw_Table). 528 -- Before the second pass executes, From and To actually reference index 529 -- in the internal table: SCO_Table is empty. Then, at the end of the 530 -- second pass, these indexes are updated in order to reference indexes 531 -- in SCO_Table. 532 533 end record; 534 535 package SCO_Unit_Table is new Table.Table ( 536 Table_Component_Type => SCO_Unit_Table_Entry, 537 Table_Index_Type => SCO_Unit_Index, 538 Table_Low_Bound => 0, -- see note above on sorting 539 Table_Initial => 20, 540 Table_Increment => 200, 541 Table_Name => "Unit_Table"); 542 543 ----------------------- 544 -- Generic instances -- 545 ----------------------- 546 547 type SCO_Instance_Index is new Nat; 548 549 type SCO_Instance_Table_Entry is record 550 Inst_Dep_Num : Nat; 551 Inst_Loc : Source_Location; 552 -- File and source location of instantiation 553 554 Enclosing_Instance : SCO_Instance_Index; 555 end record; 556 557 package SCO_Instance_Table is new Table.Table ( 558 Table_Component_Type => SCO_Instance_Table_Entry, 559 Table_Index_Type => SCO_Instance_Index, 560 Table_Low_Bound => 1, 561 Table_Initial => 20, 562 Table_Increment => 200, 563 Table_Name => "Instance_Table"); 564 565 ----------------- 566 -- Subprograms -- 567 ----------------- 568 569 procedure Initialize; 570 -- Reset tables for a new compilation 571 572end SCOs; 573