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